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

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

给定 target = 5，返回 true。
给定 target = 20，返回 false。

限制：

0 <= n <= 1000
0 <= m <= 1000

Java代码

暴力解法

简单粗暴两层遍历挨个找。

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

官方解法

从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。

注意：可以证明这种方法不会错过目标值。如果当前元素大于目标值，说明当前元素的下边的所有元素都一定大于目标值，因此往下查找不可能找到目标值，往左查找可能找到目标值。如果当前元素小于目标值，说明当前元素的左边的所有元素都一定小于目标值，因此往左查找不可能找到目标值，往下查找可能找到目标值。

class Solution {
    
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
    
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
            return false;
        }
        int row=0,column=matrix[0].length-1;
        while(row<matrix.length&&column>=0){
    
           if(matrix[row][column]==target){
    
               return true;
           }else if(matrix[row][column]<target){
    
               row++;
           }else{
    
               column--;
           }
        }
        
        return false;
    }
}

补充思路：

关键是要能够想到，从二维数组的右上角开始遍历。

• 因为左上和右下角分别是数组的最大值和最小值，所有有两个方向可以同时选择，无法确定唯一。
• 而左下和右上就可以，就拿右上角举例，它是行的最大值，列的最小值。如果它比目标值小，就可以排除这一行数据，列+1（因为它已经是这一行的最大值，比目标值还小，说明这一行数据都太小了，不可能有目标值。故列+1舍弃。）

还有另一种思路就是：

• 在右上角看。这个矩阵其实就像是一个Binary Search Tree二叉查找树。