题目
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
注意：本题与主站 240 题相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法
动态规划
最容易想到的就是动态规划。
class Solution:
def __init__(self):
self.ans = False # 类似全局变量
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 怎么想也是一个动态规划的题目
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
self.naive_walk(matrix,target,0,0)
return self.ans
# 超时
def naive_walk(self, matrix,target,i,j):
if i>=len(matrix) or j >=len(matrix[0]):
return
if self.ans == True:
return
n = matrix[i][j]
if target == n:
self.ans = True
return
if n > target:
return
self.naive_walk(matrix,target,i,j+1)
self.naive_walk(matrix,target,i+1,j)
然而这个超时了，主要的问题是复杂度为m*n.
从右上角开始
要充分利用数组的顺序，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
从左上角开始选择的话，需要回溯很多次。但是从右上角开始的话，如果当前值比较小的话，就往下，当前值比较大的话，就往左。甚至不需要回溯就能完成。
递归版本和非递归版本：
class Solution:
def __init__(self):
self.ans = False
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 怎么想也是一个动态规划的题目
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
self.walk_right(matrix,target,0,len(matrix[0])-1)
# self.ans = self.easy_walk(matrix,target)
return self.ans
def walk_right(self, matrix,target, i, j):
if i >= len(matrix) or j < 0:
return
#print(i,j)
num = matrix[i][j]
if num == target:
self.ans = True
return
if num < target:
self.walk_right(matrix,target,i+1,j)
else:
self.walk_right(matrix,target,i,j-1)
def easy_walk(self, matrix,target):
if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
return False
i = 0
j = len(matrix[0])-1
while i<len(matrix) and j >=0 :
num = matrix[i][j]
if num == target:
return True
if num > target:
j -= 1
if num < target:
i += 1
return False
总结
这一题主要是想到了从右上角开始的思路就好了。
** 踩过的坑 **
如果写成这样：
if matrix[i][j] > target: j -= 1
if matrix[i][j] < target: i += 1
if matrix[i][j] == target: return True
这样在i+1或者j-1的时候已经越界了，还去取值会出错！
同时，有时候i j 已经偏移了，这时候取得的 matrix[i][j] 不是当前要判断的值。
