剑指offer学习（Java）——面试题4：二维数组中的查找

一时失言乱红尘 2022-05-22 09:11 135阅读 0赞

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

当然可以直接遍历数组，那么时间复杂度就是O(m\*n)，要充分利用数组行有序和列有序的特点。一维数组有序时查找可以用二分查找，其时间复杂度是O(logn)。

这里也尝试二分查找，首先选取二维数组中的一个数字，

若这个数小于要查找的数字，那么待查找的数字只可能出现在右边的所有列或者下面的所有行，

若这个数大于要查找的数字，那么待查找的数字只可能出现在左边的所有列或者上面的所有行。

![70][]

但是这样就有两个区域，而且有重叠，

我们换一下选取数字的位置，

左上角和右下角于事无补，

**左下角**：

若这个数**小于**要查找的数字，那么待查找的数字只可能出现在**右边的所有列**，剔除当前列，重复之前的操作，继续判断

若这个数**大于**要查找的数字，那么待查找的数字只可能出现在**上面的所有行**，剔除当前行，重复之前的操作，继续判断

**右上角**：

若这个数**小于**要查找的数字，那么待查找的数字只可能出现在**下面的所有行**，剔除当前行，重复之前的操作，继续判断

若这个数**大于**要查找的数字，那么待查找的数字只可能出现在**左边的所有列**，剔除当前列，重复之前的操作，继续判断

选取左下角的代码如下

public class Solution {
        public boolean Find(int target, int [][] array) {
            int hang = array.length;
            int lie = array[0].length;
            for(int i=hang-1,j = 0;i>=0&&j<lie;){
            	if(target == array[i][j]) return true;
                else if(target > array[i][j]) {j++;continue;}
                else {i--;continue;}
            }
            return false;
        }
    }

选取右上角的代码如下

public class Solution {
        public boolean Find(int target, int [][] array) {
            int hang = array.length;
            int lie = array[0].length;
            for(int i=0,j = lie-1;i<hang&&j>=0;){
            	if(target == array[i][j]) return true;
                else if(target > array[i][j]) {i++;continue;}
                else {j--;continue;}
            }
            return false;
        }
    }

题目可以在牛客网练习，[二维数组中的查找][Link 1]，这里假设了输入的数组不为空，实际还要做一些特殊输入判断。

我第一个看到这个题自己的思路是，既然每一行是有序的，就可以逐行使用归并排序，最后得到一个有序的一维数组，再使用二分查找，不过显然时间复杂度和空间复杂度都比以上方法高。以上方法最差的时间复杂度是O(m+n)。

[70]: /images/20220522/af696b13fcc14776a7c52fa9b71fb612.png
[Link 1]: https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking