题目来源:牛客网/剑指offer/1.二维数组的查找
python 2 语法:
1.二维数组
行数:len(array) 列数: len(array[0])
2.循环格式
while 循环条件:
3.分支格式
if 条件1:
blankspaces 执行语句
elif 条件2:
blankspaces 执行语句
else:
blankspaces 执行语句
4.不同于C语言的几点
循环、分支结构无小括号(),以分号代替。
代码块无大括号{},以缩进表示。
每行语句没有分号。
变量使用不用定义,直接使用。
bool变量首字母大写:True/False。
算法思路:
若采用传统的二维数组遍历方式,时间复杂度为O(m*n);
本题应充分认识到数组行和列之间的有序性,找准遍历起点元素,通过待查元素与其比较大小,可批量缩小查找的范围。这里找的起点元素为第一行最后一个,因为同行中的左边元素都比他小,同列中的下边元素都比他大,通过比较大小关系,不断找到下一个比较元素,因而时间复杂度仅O(m+n)。
算法代码:
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
row_count = len(array)
column_count = len(array[0])
i = 0
j =column_count -1
while i < row_count and j >=0:
value = array[i][j];
if value == target:
return True
elif value < target:
i = i + 1
else:
j = j - 1
return False



