【力扣算法】240-搜索二维矩阵II

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

题解

无官方题解

网友题解：

• 从最右上角的元素开始找，如果这个元素比target大，则说明找更小的，往左走；如果这个元素比target小，则说明应该找更大的，往下走。
• 画个图看代码就很容易理解，总之就是从右上角开始找，如果矩阵的元素小了就往下走，如果矩阵元素大了就往左走。如果某个时刻相等了，就说明找到了，如果一直走出矩阵边界了还没找到，则说明不存在。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1){
            return false;
        }
        //起点为最左上角的元素
        int row = 0, col = matrix[0].length - 1;
        //判断当前数组元素和target，如果当前大于target，往左走；小与target，往下走
        while(row < matrix.length && col >= 0){
            if(matrix[row][col] < target){
                row++;
            }else if(matrix[row][col] > target){
                col--;
            }else{
                return true;
            }
        }
        //走出边界了还没找到，说明不存在，返回false
        return false;
    }
}

执行用时 : 13 ms, 在Search a 2D Matrix II的Java提交中击败了86.52% 的用户

内存消耗 : 51.9 MB, 在Search a 2D Matrix II的Java提交中击败了34.62% 的用户

感想

写了个很慢的解答。。。思路就是很简单的分治，从左上角出发分为右侧、下侧、右下三部分去查找。

感觉看到别人从右上或者左下开始查找的思路，一下就发现自己的愚蠢了。。。右下和左下出发感觉就相当于二分法了，简单多了。

执行用时 : 66 ms, 在Search a 2D Matrix II的Java提交中击败了5.04% 的用户

内存消耗 : 51.9 MB, 在Search a 2D Matrix II的Java提交中击败了34.84% 的用户

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        return searchMatrixSub(matrix, target, 0, 0);
    }
    private boolean searchMatrixSub(int[][] matrix, int target, int row, int col){
        if(matrix.length == 0) return false;
        else if(matrix[0].length == 0) return false;
        if(matrix[row][col] == target) return true;
        else if(matrix[row][col]>target) return false;
        else {
            boolean moreRow = (row<matrix.length-1);
            boolean moreCol = (col<matrix[0].length-1);
            if(moreRow&moreCol) return searchMatrixSub(matrix, target, row+1, col+1)||searchMatrixCol(matrix, target, row, col+1)||searchMatrixRow(matrix, target, row+1, col);
            else if(moreRow) return searchMatrixRow(matrix, target, row+1, col);
            else if(moreCol) return searchMatrixCol(matrix, target, row, col+1);
            else return false;
        }
    }
    private boolean searchMatrixRow(int [][]matrix, int target, int row, int col){
        if(matrix[row][col] == target) return true;
        else if(matrix[row][col]>target) return false;
        else {
            if(row<matrix.length-1) return searchMatrixRow(matrix, target, row+1, col);
            else return false;
        }
    }
    private boolean searchMatrixCol(int [][]matrix, int target, int row, int col){
        if(matrix[row][col] == target) return true;
        else if(matrix[row][col]>target) return false;
        else {
            if(col<matrix[0].length-1) return searchMatrixCol(matrix, target, row, col+1);
            else return false;
        }
    }
}