74. 搜索二维矩阵
一句话套路矩阵拉平成 [0,mn) 做一维二分
题目描述
给你一个满足下述两条属性的 m x n 整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。
你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出:true
示例 2:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出:false
提示:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
思路
时间
O(log(mn))空间
O(1)前提(与 Q240 的区别)
每行递增,且「下一行首元素 > 上一行末元素」,所以整块矩阵拉平后是一个有序数组 -> 直接在 [0, m*n) 上二分,不用写二维逻辑。
映射
mid -> matrix[mid / n][mid % n]
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0074 {
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false; // 防 matrix[0] 越界
const int R = (int)matrix.size(), C = (int)matrix[0].size();
int lo = 0, hi = R * C - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int v = matrix[mid / C][mid % C];
if (v == target)
return true;
else if (v < target)
lo = mid + 1;
else
hi = mid - 1;
}
return false;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0074::Solution s;
vector<vector<int>> m{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
CHECK_TRUE(s.searchMatrix(m, 3));
CHECK_FALSE(s.searchMatrix(m, 13));
CHECK_TRUE(s.searchMatrix(m, 1)); // 第一个元素
CHECK_TRUE(s.searchMatrix(m, 60)); // 最后一个元素
vector<vector<int>> one{{5}};
CHECK_TRUE(s.searchMatrix(one, 5));
CHECK_FALSE(s.searchMatrix(one, 4));
vector<vector<int>> none{}; // 空矩阵:不守卫就是 matrix[0] 越界
CHECK_FALSE(s.searchMatrix(none, 1));