• 3、如果matrix[i][j] < target，i++，排除一行。
  • 4、如果matrix[i][j] > target，j--，排除一列。
  • 5、如果出界还未找到target，则返回false。

时间复杂度分析： 每一步会排除一行或者一列，矩阵一共有 nnn 行，mmm 列，所以最多会进行n+mn+mn+m步。所以时间复杂度是 O(n+m)O(n+m)O(n+m)。

3、c++代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(!matrix.size() && !matrix[0].size()) return false;
        int i = 0, j = matrix[0].size() - 1;  //矩阵右上角
        while(i < matrix.size() && j >= 0)
        {
            if(matrix[i][j] == target)  return true;
            else if( matrix[i][j] < target) i++;  //排除一行
            else if( matrix[i][j] > target) j--;  //排除一列
        }
        return false;
    }
};
复制代码

4、java代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 && matrix[0].length == 0) return false;
        int i = 0, j = matrix[0].length - 1;  //矩阵右上角
        while(i < matrix.length && j >= 0)
        {
            if(matrix[i][j] == target)  return true;
            else if( matrix[i][j] < target) i++;  //排除一行
            else if( matrix[i][j] > target) j--;  //排除一列
        }
        return false;
    }
}
复制代码

原题链接： 240. 搜索二维矩阵 II


作者：林深时不见鹿
链接：https://juejin.cn/post/7031785113931218951
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。