面试题04. 二维数组中的查找


最近leetcode出了剑指offer的题,我们来看下这个题

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
 
示例:
 
现有矩阵 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。
 
 
限制:
 
0 <= n <= 1000
 
0 <= m <= 1000

分析

这题是从给定二维数组里面找到目标值看是否存在,最暴力的方法自然是遍历一遍。然而人家给的数组是有规律的,我们研究下:

每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。

所以数组左上角,右下角分别是最小,最大的值。

再看左下角,右上角。

这两个点是对称的。我们拿左下角举例:如果我们要找的数字大于左下角那么可以直接排除[1,2,3,10,18]一列,如果数字小于左下角排除[18, 21, 23, 26, 30]一行,感觉效率提升飞起啊。

我们可以从左下角开始设变量x,target<x则排除 x所在行(x是这一行最小的)接着去x上边寻找,target>x则排除x所在列(x是这一列中最大的)接着去x右边寻找。

右上角同理。

代码选左下角开始寻找:

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

        int xmax = matrix.length - 1;
        int ymax = matrix[0].length - 1;
        if (target > matrix[xmax][ymax] || target < matrix[0][0]) {
            return false;
        }

        int i = xmax;
        for (int j = 0; j <= ymax; j++) {
            if (target < matrix[i][j]) {//target>x时,x向上移动
                if(i==0)
                    return false;
                i--;
                j--;
            }else if(target == matrix[i][j]){
                return true;
            }else{ //target<x时,j++,x向右移动
                continue;
            }
           
        }

        return false;
    }

  • 作者:低调做个路人 (扫码联系作者)
  • 发表时间:2020-02-27 10:49:02
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 评论