这道题直接暴力AC的，虽然也能过，但是耗时太长了。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int edge = min(matrix.size(), matrix[0].size()) - 1;
//先在edge * edge的矩阵中搜索
for(int i = 0; i <= edge; ++i){
if(matrix[i][i] >= target){ //结果可能分布在edge * edge的矩阵中
//横向搜索
for(int j = i; j >= 0; --j){
if(matrix[i][j] == target) //找到target
return true;
}
//纵向搜索
for(int j = i; j >= 0; --j){
if(matrix[j][i] == target) //找到target
return true;
}
}
}
//在剩余部分（如果有的话）搜索
if(matrix.size() > matrix[0].size()){ //行数大于列数
for(int i = edge + 1; i < matrix.size(); ++i){
for(int j = 0; j < matrix[0].size(); ++j){
if(matrix[i][j] == target) //找到tarfget
return true;
}
}
}
else{ //列数大于行数
for(int i = 0; i < matrix.size(); ++i){
for(int j = edge + 1; j < matrix[0].size(); ++j){
if(matrix[i][j] == target) //找到tarfget
return true;
}
}
}
return false;
}
};
AC之后看了下灵神和Krahets的题解，感觉两位大佬的思路都很相近，只不过一个从矩阵的右上角开始比较，一个从矩阵的左下角开始比较，这里我就主要讲一下Krahets的思路，还挺通俗易懂的。
我们直接找到矩阵最左下角的元素，假设为matrix[i][j],如果matrix[i][j] == target，则直接返回true，如果matrix[i][j] > target，说明第i列可以直接舍弃，因为第i行的元素全都大于target，直接--i，如果matrix[i][j] < target，说明第j列可以直接舍弃，因为第j列的元素全部小于target，直接++j。当i < 0或j >= matrix[0].size()时终止搜寻，直接返回false。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i = matrix.size() - 1;
int j = 0;
while(i >= 0 && j <= matrix[0].size() - 1){
if(matrix[i][j] == target)
return true;
else if(matrix[i][j] > target)
--i;
else ++j;
}
return false;
}
};