LeetCode | 搜索二维矩阵

分类：二分查找 / 数组 / 矩阵

题目#

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

讲解#

二分法。

一维二分#

看成一维数组，在 [0, m * n) 这个范围里做二分，找第一个大于等于 target 的位置。

两次二分#

第二种方法是做两次二分。

第一次二分先找 target 可能在哪一行。

找到这一行之后，再对这一行做一次普通二分查找。

复杂度#

一维二分：
- 时间复杂度：O(log(m * n))
- 空间复杂度：O(1)
两次二分：
- 时间复杂度：O(log(m) + log(n))
- 空间复杂度：O(1)

因为 log(m) + log(n) = log(m * n)，所以两种方法的时间复杂度本质上是一样的。

代码#

一维二分#

源码#

1
from typing import List
2

3

4
class Solution:
5
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
6
        m = len(matrix)
7
        n = len(matrix[0])
8
        left = 0
9
        right = m * n
10

11
        while left < right:
12
            mid = (left + right) // 2
13
            x = matrix[mid // n][mid % n]
14
            if x < target:
15
                left = mid + 1
16
            else:
17
                right = mid
18

19
        return left < m * n and matrix[left // n][left % n] == target

两次二分#

源码#

1
from typing import List
2

3

4
class Solution:
5
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
6
        m = len(matrix)
7
        n = len(matrix[0])
8

9
        top = 0
10
        bottom = m - 1
11
        while top <= bottom:
12
            row = (top + bottom) // 2
13
            if matrix[row][0] <= target <= matrix[row][n - 1]:
14
                break
15
            if matrix[row][0] > target:
16
                bottom = row - 1
17
            else:
18
                top = row + 1
19

20
        if top > bottom:
21
            return False
22

23
        left = 0
24
        right = n - 1
25
        while left <= right:
26
            mid = (left + right) // 2
27
            if matrix[row][mid] == target:
28
                return True
29
            if matrix[row][mid] < target:
30
                left = mid + 1
31
            else:
32
                right = mid - 1
33

34
        return False

测试#

1
from src.python._074_Search_A_2D_Matrix import Solution
2

3

4
sol = Solution()
5

6
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
7
assert sol.searchMatrix(matrix, 3) is True
8
assert sol.searchMatrix(matrix, 13) is False
9
assert sol.searchMatrix([[1]], 1) is True
10
assert sol.searchMatrix([[1]], 2) is False
11

12
print("PASS")

参考资料#

LeetCode 原题：https://leetcode.com/problems/search-a-2d-matrix/
AlgoMonster 一维二分题解：https://algo.monster/liteproblems/74
两次二分参考题解：https://blog.csdn.net/weixin_56980169/article/details/135609735

音乐

音乐

题目#

讲解#

一维二分#

两次二分#

复杂度#

代码#

一维二分#

源码#

两次二分#

源码#

测试#

参考资料#

文章分享

评论区

音乐

文章目录