剑指 Offer 04. 二维数组中的查找

题目描述

在一个 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/

解题思路

题中说了每行都是递增的，每列也是递增的。所以我们查找的时候可以利用这个特性，如果我们从左上角开始找，当目标值target大于当前值的时候，我们需要往更大的找，但这个时候无论往右找还是往下找都是比当前值大，所以我们无法确定该往哪个方向找。同理右下角也一样。
所以我们只能从右上角或者左下角开始找。以右上角为例，左边的数比它小，下边的数比它大。来画个图看一下：

这种方法叫做线性查找法。

解题代码

class Solution:
    def findNumberIn2DArray(self, matrix: list[list[int]], target: int) -> bool:
        if matrix == []:
            return False
        row, col = len(matrix)-1, len(matrix[0])-1
        i, j = 0, col
        while i <= row and j >= 0:
            if target == matrix[i][j]:
                return True
            elif target > matrix[i][j]:
                i += 1
            elif target < matrix[i][j]:
                j -= 1
        return False

执行结果

执行用时：24 ms, 在所有 Python3 提交中击败了99.56%的用户
内存消耗：18.9 MB, 在所有 Python3 提交中击败了62.82%的用户