剑指offer 04. 二维数组中的查找

前言

牛客网剑指 offer 的 66 道题，基本属于必刷题，帅地打算把 66 岛的题解大致过一遍，大家也可以跟着帅地，每日一道刷起来！每道题会提供简单的思路以及测试通过的代码。

问题描述

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

[

[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

示例1

输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
说明：存在7，返回true

示例2

输入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：false
说明：不存在3，返回false

解答思路

方法 1

一种简单的方法就是整个数组都遍历，当然，数组从左到右，从上到下都是有序的，如果你遍历整个数组的话，那就浪费了数组的局部有序性了。

如果我们从 row = 0 和col = 0开始遍历的话，发现右边的数比 array[row] [col] 大，而下边也比 array[row] [col]大，这样的话，貌似局部有序性没有派上用场

遍历不一定就一定要从 row = 0 和 col = 0开始，有时候，换个角度，一切就豁然开朗了。

实际上我们从数组的左下角开始遍历的话

1、如果array[row] [col] > target，那么 target 必定在元素 array[row] [col] 所在列的上边，则往上移动。

2、如果 array[row] [col] < target，那么target必定在元素 array[row] [col] 所在行的右边，则往右移动。

3、否则找到目的数。

这样，就完美利用到局部有序性了。代码如下：

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

此种方法对时间复杂度是O(m + n)，（m和n表示数组的长度和宽度）

当然，这里还有另外一种方法，因为每一行都是有序的，就是对每一行进行二分查找，这种方法的话，时间复杂度是 O(nlogn)，这种方法就不提供代码了。

帅地永久会员

收藏 海报 分享链接