Time: 20190918
Type: 数组

题目描述

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

思路

本题应该有三种非常直观的思路。

第一种是非常暴力的的搜索。

第二种是每行按照二分搜索方式查找，逐行遍历，总共是复杂度的算法。

第三种是对问题的更细粒度的分析。直接上看，二维数组是有序的，如果随便从数组中间选取一个数，该数比target小或者大，都有两种选择。比如说小吧，那么查找方向可以向右或者下，即去找更大的数。

这样一思考，问题好像就变得复杂了。

试着固定变量，从左下角或者右上角来看。

如果是左下角，该值是列值最大，行值最小。如果比target小，则表示本列所有数值都比target小，这一列都不中用，删除本列。

如果比target大，则表示，本行所有数值都比target大，那么本行就不中用，删除本行。

题解

第一种解法：

function Find(target, array)
{
    // write code here
    console.log(array.length)
    m = array.length
    n = array[0].length
    for(i = 0; i < m; i++) {
        for(j = 0; j < n; j++) {
            if (array[i][j] == target) {
                return true
            }
        }
    }
    return false;
}
module.exports = {
    Find : Find
};

第二种解法：

function Find(target, array)
{
    // write code here

    function binarySearch(arr) {
        // 行内二分搜索，每行遍历
        low = 0;
        high = arr.length - 1;
        // 循环只做范围缩小
        while (low + 1 < high) {
            // low与high相邻时结束
            mid = Math.floor(low + (high - low) / 2);
            if (target <= arr[mid]) {
                high = mid;
            } 
            else if (target > arr[mid]) {
                low = mid;
            }
        }

        if (arr[low] == target || arr[high] == target) {
            return true;
        } else {
            return false;
        }
    }
    for (i = 0 ; i < array.length; i++) {
        res = binarySearch(array[i]);
        if(res) {
            return true;
        }
    }
    return false;
}

module.exports = {
    Find : Find
};

第三种解法

function Find(target, array)
{
    // write code here
    row = array.length - 1;
    col = 0;
    while (row >= 0 && col <= array[0].length - 1) {
        if (array[row][col] == target) {
            return true;
        }
        else if (array[row][col] < target) {
            // 当前列最大值小于target，该列删去
            col++;
        } 
        else {
            // 当前行最小值大于target，向上搜索，该行删去
            row--;
        }
    }
    return false;
}
module.exports = {
    Find : Find
};

END.