HHot 100C++ 图解

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
  • -109 <= matrix[i][j] <= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109

思路

时间O(m+n)
空间O(1)

思路

从右上角出发的「阶梯下降」。该位置比 target 大 -> 整列太大,左移;

比 target 小 -> 整行太小,下移。每步排除一行或一列。

易错

不能从左上角或右下角出发 —— 那两个方向「大小关系」是不确定的。

图解

j0 j1 j2 j3 j4 i0 1 4 7 11 15 i1 2 5 8 12 19 i2 3 6 9 16 22 i3 10 13 14 17 24 i4 18 21 23 26 30
矩阵(来自本仓库测试数据,红色格子 = 0)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/06_matrix.cpp18 行
namespace lc0240 {
class Solution {
 public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;  // 空矩阵不能取 matrix[0]
    int i = 0, j = (int)matrix[0].size() - 1;  // 右上角
    while (i < (int)matrix.size() && j >= 0) {
      if (matrix[i][j] == target)
        return true;
      else if (matrix[i][j] > target)
        --j;  // 这一列都比 target 大
      else
        ++i;  // 这一行都比 target 小
    }
    return false;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q240_search_a_2d_matrix_ii13 行
lc0240::Solution s;
vector<vector<int>> m{{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}};
CHECK_TRUE(s.searchMatrix(m, 5));
CHECK_FALSE(s.searchMatrix(m, 20));
CHECK_TRUE(s.searchMatrix(m, 1));   // 左上角
CHECK_TRUE(s.searchMatrix(m, 30));  // 右下角
vector<vector<int>> one{{-5}};
CHECK_TRUE(s.searchMatrix(one, -5));
vector<vector<int>> none{};
CHECK_FALSE(s.searchMatrix(none, 1));  // 空矩阵不越界
CHECK_FALSE(s.searchMatrix(one, -2));

↑↓ 选择↵ 打开/ 随时唤起