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

蔚落 2023-10-12 21:51 51阅读 0赞

### 一、题目描述 ###

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

#### 示例 ####

示例：  
有二维数组矩阵如下：

[
      [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.  二维数组中的查找，根据题目描述，给到一个每行从左到右、每列从上到下满足递增顺序的二维数组，并在数组中寻找给定的目标值，存在返回 true，不存在返回 false。
2.  对比一维数组中查找目标值，相同的，对于二位数组，无论是否有序，都可以通过一次完整的遍历并比较来判断是否存在，对于数组维数增加，算法的复杂度回平方增加，如果数量较大可能会超出时间限制。
3.  由于题目给出的二维数组符合一定的排序规律，因此可以利用规律来减少比较次数
    
     *  根据规律，数组最右侧元素作为一行中元素最大值，数组最上侧元素作为一列中最小值
     *  可以以右上角元素作为切入，判断与目标值的关系
     *  如果相等则返回 true；
     *  如果小于目标值，则当前行中所有元素均小于目标值，此时行数 +1，继续比较下方元素
     *  如果大于目标值，则当前列中所有元素均大于目标值，此时列数 -1，继续比较左侧元素
     *  最终最多遍历比较一行和一列即 m+n 次既可得到最终结果。

### 三、AC 代码 ###

#### 遍历二维数组寻找目标值 ####

*  遍历二维数组，逐个判断是否存在目标值，存在返回true，不存在则返回false，需要判断n的平方次

public boolean findNumberIn2DArray(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;
    }

![image.png][]

#### 通过边界判断 ####

*  根据数组有序的规律，选择右上角元素，与目标值比较，如果小于，则增加行数，如果大于则减少列数，最多只需要判断 m+n 次

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

![image.png][image.png 1]

### 四、总结 ###

#### 知识点 ####

*  二维数组的遍历
 *  二位有序数组利用规律求解，寻找目标值

#### 最后 ####

剑指 Offer ，算法刷起来！[LeetCode 剑指 Offer][LeetCode _ Offer]。

[image.png]: https://img-blog.csdnimg.cn/img_convert/cfc61108b127f9f19804e1c04953917a.png
[image.png 1]: https://img-blog.csdnimg.cn/img_convert/e3f615d93e701fba32a9e25ae0b1be6a.png
[LeetCode _ Offer]: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/