【力扣】240.搜索二维矩阵 II

题目

我的代码

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[0].size();j++){if(target==matrix[i][j]){return true;}else if(target<matrix[i][j]){break;}}if(matrix[i][0]>target){break;}}return false;}
};

Z字搜索法

我的解法实在招笑，自以为优化了，其实优化了个寂寞，一看答案惊为天人。

思路：

我们可以从矩阵 matrix 的右上角 (0,n−1) 进行搜索。在每一步的搜索过程中，如果我们位于位置 (x,y)，那么我们希望在以 matrix 的左下角为左下角、以 (x,y) 为右上角的矩阵中进行搜索，即行的范围为 [x,m−1]，列的范围为 [0,y]：

    如果 matrix[x,y]=target，说明搜索完成；

    如果 matrix[x,y]>target，由于每一列的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 y 列的元素都是严格大于 target 的，因此我们可以将它们全部忽略，即将 y 减少 1；

    如果 matrix[x,y]<target，由于每一行的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 x 行的元素都是严格小于 target 的，因此我们可以将它们全部忽略，即将 x 增加 1。

在搜索的过程中，如果我们超出了矩阵的边界，那么说明矩阵中不存在 target。

代码与AC截图

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m=0;int n=matrix[0].size()-1;while(m<matrix.size()&&n>=0){if(target==matrix[m][n]){return true;}else if(target<matrix[m][n]){n--;}else{m++;}}return false;}
};