- 问题描述
- 每行从左到右递增
- 每列从左到右递增
- 输入一个二维数组和一个整数
- 判断数组是否有这个整数
- 举例分析
- 观察这个实际的例子，看看他有什么特征
- 假设1
- 从左上角的数字开始寻找
- 向右走数字在增大
- 向下走数字也在增大
- 那就只能通过一行一行的遍历下去？或一列一列的遍历下去吗？
- 假设2
- 从右下角开始
- 向左走数字在减小
- 向上走数字也在减小
- 本质上和第一种假设就没有区别了，它没有办法一次缩窄较大的范围，每次只能确定一个数字不是我们要找的
- 那么有没有办法可以一次判断，排除多个数字的可能性呢
- 假设3
- 从右上角开始
- 是一行中数字最大的
- 又是一列中数字最小的
- 所以当目标大于它 就是大于了一整行
- 目标小于它 就是小于了一整列
- 也就是等价于一次判断我们可以删除一整行或者是一整列
- 代码解析
- found 就是返回值 说明有没有找到这个目标数字
- 我们要知道行和列的大小，涉及到数组的时候，我们肯定会有判断条件，让我们访问的位置是不可以越界的
- 当数组不是空的时候，并且行列都不是0
- 找到右上角的横纵坐标
- 进入while循环 其中行不能过大，列不能过小
- 如果当前右上角的数字就是目标数字，found改成true，跳出整个循环
- 如果当前值大于目标值，列--
- 如果当前值小于目标值，行++
- 返回found的值
class Solution:
# array 二维列表
def Find(self, target, array):
xend = len(array)-1
yend = len(array[0])-1
x = 0
while x <= xend and yend >= 0:
if array[x][yend] == target:
return True
elif array[x][yend] > target:
yend -= 1
else:
x += 1
return False