题目描述

LeetCode 240. 搜索二维矩阵 II

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

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

示例 1：

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

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

方法一：一维二分查找

思路与算法

由于矩阵 \(\textit{matrix}\) 中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找，判断 \(\textit{target}\) 是否在该行中，从而判断 \(\textit{target}\)是否出现。

代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (const auto& row: matrix) {
            auto it = lower_bound(row.begin(), row.end(), target);
            if (it != row.end() && *it == target) {
                return true;
            }
        }
        return false;
    }
};

复杂度分析

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

方法二：Z 字形线性查找

假设现有矩阵 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]
]

假设我们需要查找matrix[1][2] = 8, 由于每一行的元素都是升序排列的，每一列的元素都是升序排列的，那么：

右下角的数一定都比8大：

[
  [8, 12, 19],
  [9, 16, 22],
  [14, 17, 24],
  [23, 26, 30]
]

左上角的数一定都比8小：

[
  [1,   4,  7],
  [2,   5,  8]
]

故而这两块都可以直接排除。

那么剩下的左下角的数和右上角的数与8的大小关系不知道如何，故而只需要验证这两块即可：

//右上角
[
  [7, 11, 15],
  [8, 12, 19]
]

//左下角
[
  [2,   5,  8],
  [3,   6,  9],
  [10, 13, 14],
  [18, 21, 23]
]

我们可以看到，矩阵中大于 mid 的数就和不大于 mid 的数分别形成了两个板块，沿着一条锯齿线将这个矩形分开。其中左上角板块的大小即为矩阵中不大于 mid 的数的数量。

考虑子问题，我们每一次都选择从右上角开始遍历，这样一来就可以排除右上角这一块的干扰。从而将问题转化为以 \(\textit{matrix}\) 的左下角为左下角、以 \((x, y)\)为右上角的矩阵新的子问题：

[
  [2,   5,  8],
  [3,   6,  9],
  [10, 13, 14],
  [18, 21, 23]
]

以右上角为起点开始逐渐缩小矩阵，这样每次只会考虑左下角这一块矩阵即可：

• 如果x < target，那么x左边的所有数字都可以排除掉。
• 如果x > target，那么x下边的所有数字都可以排除掉。

思路与算法

我们可以从矩阵 \(\textit{matrix}\) 的右上角 \((0, n-1)\)进行搜索。在每一步的搜索过程中，如果我们位于位置 \((x, y)\)，那么我们希望在以 \(\textit{matrix}\) 的左下角为左下角、以 \((x, y)\)为右上角的矩阵中进行搜索，即行的范围为\( [x, m - 1]\)，列的范围为\( [0, y]\)：

• 如果 \(\textit{matrix}[x, y] = \textit{target}\)，说明搜索完成；
• 如果 \(\textit{matrix}[x, y] > \textit{target}\)，由于每一列的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 \(y\) 列的元素都是严格大于 \(\textit{target}\) 的，因此我们可以将它们全部忽略，即将 \(y\) 减少 \(1\)；
• 如果 \(\textit{matrix}[x, y] < \textit{target}\)，由于每一行的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 \(x\) 行的元素都是严格小于 \(\textit{target}\)的，因此我们可以将它们全部忽略，即将 \(x\) 增加 \(1\)。

在搜索的过程中，如果我们超出了矩阵的边界，那么说明矩阵中不存在 \(\textit{target}\)。

代码

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;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            }
            else {
                ++x;
            }
        }
        return false;
    }
};

复杂度分析

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

补充说明

类似的题目还有：378. Kth Smallest Element in a Sorted Matrix

注意 C++ Operator Precedence，取中位数应该如下：

int mid = left + ((right - left)>>1);