📝 题目描述

题目链接：搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例：

示例 1：

1
2
输入：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

示例 2：

1
2
输入：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 = 20
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -10^9 <= target <= 10^9

💡 解题思路

方法一：二分查找

首先，由于矩阵每行的元素从左到右升序排列、每列的元素从上到下升序排列，我们可以通过剪枝来缩小查找范围。

举例来说，对于示例二中的矩阵，如果 target = 5，那么我们通过遍历第一行[1 4 7 11 15]，可以确定 target 肯定只会出现在[1 4]两列，因为后面的列的首个值（最小值）已经大于5，肯定后续元素也会大于5；同理，遍历第一列，我们可以确定 target 只会出现在[1 2 3]这三列中。通过这样的剪枝，我们把查找范围从5×55 \times 5缩小到了3×23 \times 2。

因此当我们收到 target 时，可以通过遍历首行的每个元素、每列的首个元素，缩小要查找的范围。

接下来我们可以从缩小后的范围中，按行遍历，通过二分法进一步提高效率。

方法二：优化解法

我们可以使用类似二叉树的思路，将起点放在右上角（或左下角）。

以右上角（x, y）为例，向左走，元素会变小，向下走，元素会变大。

因此我们可以不断将自身与 target 比较，并根据结果调整位置，直到找到 target 或走出矩阵边界。

🔧 代码实现

1、二分查找

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
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 获取 m 和 n 的值
        int m = matrix.size(), n = matrix[0].size();
        bool ans = false;
        // 剪枝一：看target是否在整个矩阵的最大值与最小值的范围内
        if ( target < matrix[0][0] || target > matrix[m - 1][n - 1] ) {
            return false;
        }
        // 剪枝二：利用矩阵性质缩小查找范围
        int end_row = m - 1, end_col = n - 1;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] < target) {
                end_row = i;
            } else if (matrix[i][0] > target) {
                break;
            } else {
                return true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] < target) {
                end_col = j;
            } else if (matrix[0][j] > target) {
                break;
            } else {
                return true;
            }
        }
        // 使用二分法遍历每行查找
        for (int i = 0; i <= end_row; i++) {
            // 剪枝三：如果最后一个元素小于target，跳过该行
            if (matrix[i][end_col] < target) {
                continue;
            } else if (matrix[i][end_col] == target) {
                return true;
            }
            // 手动实现二分法
            // int left = 0, right = end_col;
            // while (left <= right) {
            //     int mid = left + (right - left) / 2;
            //     if (matrix[i][mid] == target) {
            //         return true;
            //     } else if (matrix[i][mid] < target) {
            //         left = mid + 1;
            //     } else {
            //         right = mid - 1;
            //     }
            // }
            // 调库二分法 [左闭右开)
            // lower_bound：在一个已排序的范围内，查找第一个不小于（即 >=）给定值的元素，返回指向该元素的迭代器。
            // upper_bound：找第一个 > value 的位置
            auto it = lower_bound(matrix[i].begin(), matrix[i].begin() + end_col + 1, target, less<int>());
            if (it != (matrix[i].begin() + end_col + 1) && *it == target) {
                return true;
            }
        }
        return ans;
    }
};

2、Z字查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n - 1;
        bool ans = false;
        while(x < m && y >= 0) {
            if (matrix[x][y] < target) {
                x++;
            } else if (matrix[x][y] > target) {
                y--;
            } else {
                return true;
            }
        }
        return ans;
    }
};

📊 复杂度分析

1、二分查找

  • 时间复杂度：O(mlogn)O(mlogn)。对一行使用二分查找的时间复杂度为 O(logn)，最多需要进行 m 次二分查找。
  • 空间复杂度：O(1)O(1)。

2、Z字查找

  • 时间复杂度：O(m+n)O(m + n)：在搜索的过程中，如果我们没有找到 target，那么我们要么将 y 减少 1，要么将 x 增加 1。由于 (x,y) 的初始值分别为 (0,n−1)，因此 y 最多能被减少 n 次，x 最多能被增加 m 次，总搜索次数为 m+n。在这之后，x 和 y 就会超出矩阵的边界。
  • 空间复杂度：O(1)O(1)。

🎯 总结

  • 核心思想：掌握二分查找的写法。