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.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
-109 <= target <= 109
思路
时间
O(m+n)空间
O(1)思路
从右上角出发的「阶梯下降」。该位置比 target 大 -> 整列太大,左移;
比 target 小 -> 整行太小,下移。每步排除一行或一列。
易错
不能从左上角或右下角出发 —— 那两个方向「大小关系」是不确定的。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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));