题目

在一个 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] 不是当前要判断的值。