每日一题《剑指offer》数组篇之二维数组中的查找

终有救赎

发布于 2023-10-16 10:16:50

1840

发布于 2023-10-16 10:16:50

文章被收录于专栏：多线程

题目链接：二维数组中的查找

JZ4 二维数组中的查找

难度：中等

描述

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

数据范围

数据范围：矩阵的长宽满足0≤n,m≤500,矩阵中的值满足 0≤val≤10^9

进阶：空间复杂度O(1),时间复杂度O(n+m)

举例

比如在下面的二维数组中查找数字7，查找过程如下：

解题思路

很明显，由于该二维数组上到下递增，左到右递增的特殊性，遍历整个矩阵进行查找不是该题目的意图所在。总结规律我们可以发现：应该从矩阵的右上角或者左下角开始查找。

以右上角为例，首先选取右上角的数字，如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则说明该列其他元素都大于要查找的数字，便可以删掉该列；如果该数字小于要查找的数字，则说明该行其他元素也都小于要查找的数字，便可以删掉该行。

这样，每一次比较都可以剔除一行或者一列，进而缩小查找范围，时间复杂度为O(n) 。

编程实现（java）

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
       //如果数组为空，则直接返回false
        if(matrix==null || matrix.length == 0 ) {
            return false;
        }
        //从右上角开始找
        int i=0,j=0;
        for(i =0,j=matrix[0].length-1; i<matrix.length && j>=0;) {
            if(matrix[i][j] == target) {
                return true;                //如果找到直接返回true
            }
            else if(matrix[i][j]>target) {   //如果该值大于查找值，跳过该列
                j--;
            }
            else {                          //如果该值小于查找值，跳过该行
                i++;
            }
        }
        return false;                       //最后记得返回false，不然会报错
    }
}