欢迎访问LeetCode题解合集
题目描述
编写一个高效的算法来判断 m x 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.length$
-
$n == matrix[i].length$
-
$1 \le m, n \le 100$
-
$-10^4 \le matrix[i][j], target \le 10^4$
题解:
法一:
因为矩阵保证每行递增,且前一行的最后一个元素小于当前行的第一个元素,于是可以根据最后一列快速确定 target
在哪一行,然后在行中查找。
时间复杂度:$O(n + m)$
额外空间复杂度:$O(1)$
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size();
if ( !n ) return false;
int m = matrix[0].size();
if ( !m ) return false;
int r = 0, c = m - 1;
if ( target < matrix[0][0] || target > matrix[n - 1][m - 1] )
return false;
while ( true ) {
if ( r < 0 || r >= n || c < 0 || c >= m ) return false;
if ( matrix[r][c] < target ) ++r;
else if ( matrix[r][c] > target ) --c;
else return true;
}
return false;
}
};
/*
时间:8ms,击败:66.30%
内存:9.4MB,击败:80.35%
*/
法二:
因为行和列都是有序的,所以可以使用两次二分,第一次确定 target
在哪一行,第二次确定在那一列。
时间复杂度:$O(logn + logm)$
额外空间复杂度:$O(1)$
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size();
if ( !n ) return false;
int m = matrix[0].size();
if ( !m ) return false;
if ( target < matrix[0][0] || target > matrix[n - 1][m - 1] )
return false;
int l = 0, r = n - 1, mid;
while ( l < r ) {
mid = ( l + r ) >> 1;
if ( matrix[mid][m - 1] == target ) return true;
if ( matrix[mid][m - 1] >= target ) r = mid;
else l = mid + 1;
}
int row = r;
if ( target < matrix[r][0] ) return false;
l = 0, r = m - 1;
while ( l < r ) {
mid = ( l + r ) >> 1;
if ( matrix[row][mid] == target ) return true;
if ( matrix[row][mid] >= target ) r = mid;
else l = mid + 1;
}
return matrix[row][r] == target;
}
};
/*
时间:4ms,击败:95.74%
内存:9.3MB,击败:84.15%
*/
法三:
也可以将整个矩阵展开成一维数组,在一维数组上一次二分即可。
时间复杂度:$O(log(n*m))$
额外空间复杂度:$O(1)$
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size();
if ( !n ) return false;
int m = matrix[0].size();
if ( !m ) return false;
if ( target < matrix[0][0] || target > matrix[n - 1][m - 1] )
return false;
int l = 0, r = n * m - 1, mid;
int val;
while ( l < r ) {
mid = ( l + r ) >> 1;
val = matrix[mid / m][mid % m];
if ( val == target ) return true;
if ( val > target ) r = mid;
else l = mid + 1;
}
return matrix[r / m][r % m] == target;
}
};
/*
时间:4ms,击败:95.74%
内存:9.3MB,击败:82.28%
*/
与 方法二 时间复杂度一样,不过代码更简洁。