【LeetCode】字节面试-行、列递增的二维数组数字查找

行、列递增的二维数组数字查找

题目描述：剑指offer 04力扣

给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。

示例:

现有矩阵 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。

解题思路：

由于数组是按序排列的，因此我们可以灵活的找到以一个数位起点，如target大于或小于该数，则查找范围减少一行或者一列。观察可以发现数组的左下角数或右上角两个数都可以作为起点。
注意数组可能为空数组，
以测试题为例：选取matrix左下角那个数18为起点，18 > 5说明target一定在数组的上方、故上移一行到10，同理直到 3 < 5说明target一定在该数右边、故右移一列到6，以此类推，直到找到target，若超出数组范围还没找到则返回False。

代码：

class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0:	# 如若数组为空，则直接返回无需再进行查找
            return False
        else:
            n = len(matrix)    # 得到数组大小
            m = len(matrix[0])
            i, j = n-1, 0  
            while i >= 0 and j < m:
                if matrix[i][j] > target: 
                    i -= 1
                elif matrix[i][j] < target: 
                    j += 1
                else: 
                    return True
            return False

复杂度分析

时间复杂度：O(n+m)。访问到的下标的行最多增加 n 次，列最多减少 m 次，因此循环体最多执行 n + m 次。
空间复杂度：O(1)。