【Leetcode】剑指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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

WA代码

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        if matrix == []:
            return False
        elif matrix == [[]]:
            return False

        m = len(matrix[0])
        xi = 0
        xj = n - 1
        xmid = int((xi + xj) / 2)
        while xi != xmid and xj != xmid:
            temp = matrix[xmid][m-1]
            if temp == target:
                return True
            elif temp > target:
                xj = xmid
            else:
                xi = xmid
            xmid = int((xi + xj) / 2)


        return self.findNumInList(matrix[xi], matrix, target) or self.findNumInList(matrix[xj], matrix, target)


    def findNumInList(self, targetlist, matrix, target):
        yi = 0
        yj = len(matrix[0]) - 1
        ymid = int((yi + yj) / 2)

        if targetlist[ymid] == target:
            return True
        if len(matrix[0]) == 2:
            return target == targetlist[0] or targetlist[1] == target

        while yi != ymid and yj != ymid:
            temp = targetlist[ymid]
            if temp == target:
                return True
            elif temp < target:
                yi = ymid
            else:
                yj = ymid
            ymid = int((yi + yj) / 2)
        else:
            if target == targetlist[0] or target == targetlist[-1]:
                return True
            else:
                return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

笔者最开始解题的时候，想着从以最下方中点或者最右方中点为界二分，确定了所在行或者所在列之后，再进行二分查找。然而这种做法首先需要大量的补丁，其次无法解决
[[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 7, 9],
[1, 8, 9, 11]]
查找7的这个过程。这是因为xij+1和xi+1j是无法确定大小关系的。因此，本质上来说这个解法是错误的。

AC代码

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)

        if matrix == []:
            return False
        elif matrix == [[]]:
            return False

        m = len(matrix[0])

        i = 0
        j = m - 1
        while i < n and j >= 0:
            if target == matrix[i][j]:
                return True
            elif target > matrix[i][j]:
                i += 1
            else:
                j -= 1
        else:
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

事实上，仔细观察可以发现，从右上角的视角来看，整个矩阵呈现一颗二叉排序树的样子。因此通过横纵坐标的变化可以迅速解决该问题，判定条件为坐标越界。