题目描述
74. 搜索二维矩阵
难度中等
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
样例
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
输出:true
示例 2:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
输出:false
示例 3:
输入:matrix = [], target = 0
输出:false
提示:
m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4
解法一:展开二分
(二分) $O(logn)$
我们可以想象把整个矩阵,按行展开成一个一维数组,那么这个一维数组单调递增,然后直接二分即可。
二分时可以通过整除和取模运算得到二维数组的坐标。
row = mid / n;
col = mid % n;
时间复杂度分析:二分的时间复杂度是 $O(logn^2) = O(logn)$
C++ 代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
if (m == 0 || n == 0) return false;
int l = 0, r = m * n - 1;
while (l < r) {
int mid = l + r >> 1;
if (matrix[mid / n][mid % n] >= target) r = mid;
else l = mid + 1;
}
return matrix[r / n][r % n] == target;
// return matrix[l / n][l % n] == target;
}
};
解法二:单调性扫描
(单调性扫描) $O(n+m)$
-
初始化
row = 0
,col = n - 1
,从右上角元素开始。 -
如果发现
matrix[row][col] == target
,则直接返回true
; -
若
target < matrix[row][col]
,则向左移动col--
; -
若
target > matrix[row][col]
,则向下移动row--
; -
如果出界返回 false。
时间复杂度:
可以看到每次 row
向下移动或者 col
向左移动,移动次数不超过 n+m
次,故时间复杂度为 $O(n+m)$。
C++ 代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
if (m == 0 || n == 0) return false;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
int t = matrix[row][col];
if (t == target) return true;
if (target < t) col--;
else row++;
}
return false;
}
};
解法三:四个方向二分压缩
(二分) $O(k(logn+logm))$
- 初始化上下左右边界
up
,down
,left
,right
,保证target
可能出现在此区域。 - 每次在
up
行中,二分求出新的right
;在down
行中,二分求出新的left
; - 接着在
2
求出的left
列中,二分求出新的down
;在2
求出的right
列中,二分求出新的up
; - 如果
up == down
&&left == right
,则判断matrix[up][left] == target
。 - 注意,如果一轮迭代更新中,四个元素的值都没有变化,则说明那一片区域有多个
target
,直接返回true
。
时间复杂度:
-
每次迭代时间复杂度为
O(logn+logm)
,假设需要k
次迭代,故时间复杂度为 $O(k(logn+logm))$。 -
最坏情况可能
k=min(n,m)
,但平均情况下很难达到最坏情况。
空间复杂度:
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int up = 0, down = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;
int l, r;
while(left < right || up < down) {
int new_left, new_right, new_up, new_down;
// new_right: find the last element in up row that is <= target
l = left, r = right;
while (l < r) {
int m = l + r + 1 >> 1;
if (matrix[up][m] <= target)
l = m;
else
r = m - 1;
}
new_right = l;
// new_up: find the first element in new_right column that is >= target
l = up, r = down;
while (l < r) {
int m = l + r >> 1;
if (matrix[m][new_right] >= target)
r = m;
else
l = m + 1;
}
new_up = l;
// new_left: find the first element in down row that is >= target
l = left, r = right;
while (l < r) {
int m = l + r >> 1;
if (matrix[down][m] >= target)
r = m;
else
l = m + 1;
}
new_left = l;
// new_down: find the last element in new_left column that is <= target
l = up, r = down;
while (l < r) {
int m = l + r + 1 >> 1;
if (matrix[m][new_left] <= target)
l = m;
else
r = m - 1;
}
new_down = l;
// if left, right, up, down stops updating. The whole square is target
if (left == new_left && right == new_right && up == new_up && down == new_down)
return true;
right = new_right;
up = new_up;
left = new_left;
down = new_down;
}
return matrix[up][right] == target;
}
};
解法四:右上两个方向往左下二分压缩
思路和解法三一样,但可以少写一半的代码。
- 写法一:while (l <= r)
- 写法二:while (l < r)
C++ 代码
写法一:
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
if (m == 0 || n == 0) return false;
int up = 0, down = m - 1, left = 0, right = n - 1;
int new_up = 0, new_right = 0;
int l, r;
while(left < right || up < down) {
// new_right: 找到最后一个小于等于 target 的数
l = left, r = right;
while (l <= r) {
int mid = l + r >> 1;
if (matrix[new_up][mid] <= target) l = mid + 1;
else r = mid - 1;
}
new_right = r;
if (new_right < left) return false;
// new_up:找第一个大于等于 target 的数
l = up, r = down;
while (l <= r) {
int mid = l + r >> 1;
if (matrix[mid][new_right] >= target) r = mid - 1;
else l = mid + 1;
}
new_up = l;
if (new_up > down) return false;
if (right == new_right && up == new_up)
return true;
right = new_right;
up = new_up;
}
return matrix[new_up][new_right] == target;
}
};
写法二:
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size(), n = matrix[0].size();
int l, r;
int up = 0, down = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;
while (left < right || up < down) {
int new_right, new_up;
// new_right: 找到最后一个小于等于 target 的数
l = left, r = right;
while (l < r) {
int m = l + r + 1 >> 1;
if (matrix[up][m] <= target) l = m;
else r = m - 1;
}
new_right = l;
// new_up:找第一个大于等于 target 的数
l = up, r = down;
while (l < r) {
int m = l + r >> 1;
if (matrix[m][new_right] >= target) r = m;
else l = m + 1;
}
new_up = r;
/*遇到的case为:单行单列以及下面的
[[1,1],[2,2]]
0
这步的return true 改为break就能AC*/
if (right == new_right && up == new_up) break;
right = new_right;
up = new_up;
}
return matrix[up][right] == target;
}
};