LeetCode hot100-21

240. 搜索二维矩阵 II

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

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

这题很神奇，因为暴力解法都可以通过

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

官方解法三
我比较喜欢Z字形这种解法。为什么选择从右上角出发。其实右上角或者左下角出发都可以。但是左上角和右下角就不行。因为需要确定当前数字不等于target时往哪边走是对的。比如从左上角出发的话，如果当前的数小于target，现在需要找更大的一个数。那往右走和往下走都是变大，就不知道应该怎么走了。但是如果从右上角开始的话，需要更大的数就往下走，需要更小的数就往左走，完全可以确定方向。

注意while条件对于y来说是>=0不是>0.数组是不会越界的，因为当y=0时如果满足等于target就跳出了，如果大于target，y变成-1后进不了循环，自然不会出现matrix[x][-1]的情况。反而while条件y不取等于会漏掉matrix[x][0]的情况。

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

作者：力扣官方题解
链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/solutions/1062538/sou-suo-er-wei-ju-zhen-ii-by-leetcode-so-9hcx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。