这道题直接暴力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) //找到targetreturn true;}//纵向搜索for(int j = i; j >= 0; --j){if(matrix[j][i] == target) //找到targetreturn 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) //找到tarfgetreturn 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) //找到tarfgetreturn 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;}
};