240 搜索二维矩阵II
https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
解法一:暴力枚举
无脑解法,没有利用题意“升序”
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for(int i = 0; i < matrix.size(); i++){
for(int j = 0; j < matrix[i].size(); j++){
if(matrix[i][j] == target)
return true;
}
}
return false;
}
};
复杂度分析
- 时间复杂度:O(mn)。
- 空间复杂度:O(1)。
解法二:二分查找
利用题意“升序”可直接二分查找
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 这里要用引用,不然会报内存超出
for(const auto &row : matrix){
auto it = lower_bound(row.begin(), row.end(), target);
if(it != row.end() && *it == target) return true;
}
return false;
}
};
解法三:二叉搜索树
https://leetcode.cn/problems/search-a-2d-matrix-ii/solutions/2361487/240-sou-suo-er-wei-ju-zhen-iitan-xin-qin-7mtf
将矩阵逆时针旋转45度,将其变成二叉搜索树
以右上角为根节点
如果超出边界,说明无解
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i = 0, j = matrix[0].size() - 1;
while(i <= matrix.size() - 1 && j >= 0 ){
if(matrix[i][j] == target) return true;
if(matrix[i][j] < target) i++;
else j--;
}
return false;
}
};