一道在剑指Offer和LeetCode中都出现的题目

原题链接

面试题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

直觉

1、特判加暴力求解

算法

• 判断 []、[[]]、[[<target]] 三种情况，直接返回 False 。
• 循环读取，依次判断。

复杂度分析

• 时间复杂度：\(O(n \times m)\)。二维数组中的每个元素都被遍历，因此时间复杂度为二维数组的大小。
• 空间复杂度：\(O(1)\)。

2、线性查找

算法

• 从二维数组的右上角开始查找。
  • 如果 当前元素等于目标值，则返回 true。
  • 如果 目标值小于当前元素，说明目标值肯定不在这一列，则移到左边一列。
  • 如果 目标值大于当前元素，说明目标值肯定不在这一行，则移到下边一行。
• 依次循环直到直到目标值，或者移动到左下角。

整个过程就是在利用条件按不断缩小区域。

复杂度分析

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

总结

为啥就是想不到这一点呢？

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-b-3/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

1、特判加暴力求解

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not len(matrix) or (len(matrix) == 1 and len(matrix[0]) == 0) \
        or target < matrix[0][0]:  return False  # 永远记住对空数组、空矩阵的预判，条件太长就换换行。
        for row in matrix:
            for item in row:
                if item == target:
                    return True
        return False

2、线性查找

# coding: utf-8
from typing import List

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        """find nuber in a matrix
        :param matrix: List[List[int]]
        :param target: int
        :return: bool
        """
        if not len(matrix) or (len(matrix) == 1 and len(matrix[0]) == 0) \
        or target < matrix[0][0]:  return False  # 永远记住对空数组、空矩阵的预判，条件太长就换换行。
        row = 0
        rows = len(matrix)
        col = len(matrix[0]) - 1
        # while row != rows - 1 and col != 0:  # 这种条件，不能通过([[-1,3]], -1)这种只有一行的测试用例了。
        while row < rows and col >= 0:  # 换成这个条件之后，就能通过([[-1,3]], -1)这种只有一行的测试用例了。
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        # return True if matrix[row][col] == target else False  # 这里不能用matrix[row][col] == target，因为最终row可能会大于rows，col可能会小于0。
        return True if matrix[rows-1][0] == target else False


if __name__ == "__main__":

    arguments = [
        [[-1,3]],
        [
            [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]
        ],
        [
            [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]
        ],
    ]
    arguments_1 = [-1, 5, 20]
    answers = [True, True, False]
    solution = Solution()
    for i in range(len(arguments)):
        result = solution.findNumberIn2DArray(arguments[i], arguments_1[i])
        print(result == answers[i])

代码陷阱

1、注意 while 条件，用 < / <= / > / >= 控制 好过 用 = / != 控制。当测试用例只有一行是，用 = / != 控制会报错。

# while row != rows - 1 and col != 0:  # 这种条件，不能通过([[-1,3]], -1)这种只有一行的测试用例了。
while row < rows and col >= 0:  # 换成这个条件之后，就能通过([[-1,3]], -1)这种只有一行的测试用例了。

2、return 时注意判断左下角那个数值是否是target

# return True if matrix[row][col] == target else False  # 这里不能用matrix[row][col] == target，因为最终row可能会大于rows，col可能会小于0。
return True if matrix[rows-1][0] == target else False