MENU

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

August 7, 2018 • Read: 207 • LeetCode

题目链接: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;
    }
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code