题目链接

剑指 Offer 04. 二维数组中的查找

思路

借鉴Krahets大神的思路，将矩阵逆时针旋转45°，可以发现其大小性质类似于二叉搜索树。

利用这个性质可以很方便的在搜索过程中剪去一行或者一列，加快搜索进度。

代码

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length == 0){
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;

        while(i < m && j >= 0){
            if(target == matrix[i][j]){
                return true;
            }else if(target < matrix[i][j]){
                j--;
            }else{
                i++;
            }
        }

        return false;
    }
}