题目描述

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

例如:

输入:16, [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
输出:false


一般情况下我们可以使用两个for循环进行遍历,代码是这样:

function Find(target, array){
    for(var i = 0;i < array.length;i++){
        for(var j = 0;j < array[i].length;j++){
            if(array[i][j] == target){
                return true;
            }
        }
    }
    return false;
}

但是这样浪费了题目中的信息,题目中说这是一个有序序列,并且子数组的长度相同,并且这样的时间复杂度是O(n^2)。


所以可以考虑其它方式,首先把数组写成二维的样式,如下:

子数组0 子数组1 子数组2 子数组3
1 2 4 6
2 4 7 8
8 9 10 11
9 12 13 15

观察得知从上至下是递增,从左至右也是递增。现在以左下角的数字9作为开始数字,对传入的数字与9相比较,如果比9小则向上移动,如果比9大则向右移动,一直重复就可以找到这个数字。
为什么不从左上角开始呢,因为左上角不管向下还是向右都是递增,这是一个分岔路口,程序不知道应该走哪边,所以选择左下角唯一的。
代码如下:

function Find(target, array) {
    var num1 = array.length;
    var num2 = array[0].length;
    for (var i = 0, j = num2 - 1; i < num1 && j >= 0;) {
        /*
            i代表列,j代表行,初始就为左下角的数字。
            i<num1是列的边界,j>=0是行的边界(子数组边界)
        */
        if (target == array[i][j]) {
            return true;
        }
        if (target > array[i][j]) {
            i++;
            continue;
        }
        if (target < array[i][j]) {
            j--;
            continue;
        }
    }
    return false;
}

当然也有一些其它方法,比如把子数组进行二分法查找,并对每个子数组都这样操作。不过这里就讨论了。