LeetCode74. 搜索二维矩阵&240. 搜索二维矩阵 II

题目链接：LeetCode74

题解

通常情况下在一个矩阵中搜索一个元素时间复杂度是O(m*n)的，但是在这里只用O(m+n)的时间复杂度就能完成，说一下思路

以右上角为起点，如果当前的值小于我要寻找的值，就往下移动，如果当前的值大于我要寻找的值，就往左移动

代码

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

题目链接：LeetCode240

代码

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