LC 240 搜索二维矩阵 II
有一个 m * n的矩阵，其中该矩阵每行从左到右升序，每列从上到下升序
给定一个target值，找到返回true，反之返回false
暴力
时间复杂度O(MN)，显然不好
二分查找
第一时间想到的，时间复杂度O(MlogN)，但显然还有优化的地方，因为都只用到了一维的有序，要么行有序，要么列有序，显然条件浪费了
代码实现如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size(), col = matrix[0].size();
for(int i = 0; i < row; i++) {
int l = 0, r = col - 1;
while(l <= r) {
int mid = (l + r) / 2;
if(target == matrix[i][mid])
return true;
if(target > matrix[i][mid])
l = mid + 1;
if(target < matrix[i][mid])
r = mid - 1;
}
}
return false;
}
|
分治
（不看题解我真的想不到系列。。。）
把矩阵的右上角设为一个端点。这么设定的原因是因为在右上角，这时候搜索的方向要么往下，要么往左，往下是升序，往左是降序，这样子会通过阶梯式的办法找到target数
如图所示，从右上角的15开始，查找目标数5
代码实现如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size(), col = matrix[0].size();
int x = 0, y = col - 1;
while(x < row && y >= 0) {
if(target == matrix[x][y])
return true;
if(target < matrix[x][y])
y--;
else if(target > matrix[x][y])
x++;
}
return false;
}
|