二维数组中的查找

题目描述

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

思路

左上角与右下角值为依题意为最值，故可先判断tatget是否在矩阵之中，之后对每一行进行查找，因每一行均为顺序且有序存储，故使用二分查找。

代码

function Find(target, array)
{
    // write code here
    function binarySearch(start, end, object, copyOfArray) {
        if(start <= end){
            if(object < copyOfArray[Math.floor((start + end) / 2)]) {
                return arguments.callee(start, Math.floor((start + end) / 2) - 1, object, copyOfArray);
            }else if(object == copyOfArray[Math.floor((start + end) / 2)]) {
                return true;
            }else if(object > copyOfArray[Math.floor((start + end) / 2)]) {
                return arguments.callee(Math.floor((start + end) / 2) + 1, end, object, copyOfArray);
            }
        }else {
            return false;
        }
    }
    
    
    var col = array[0].length;
    var row = array.length;
    
    if(target > array[row - 1][col - 1] || target < array[0][0]) {
        return false;
    }else {
        for(var j = 0; j < row; j++) {
            if(binarySearch(0, col - 1, target, array[j])) {
                return true;
            }
        }
        return false;
    }
}

运行时间：92ms
占用内存： 7860k

最优解题思路

该矩阵不仅每一行上有序，在每一列上依然有序，找到一个起始点进行搜索，易知左上与右下的极值点不符合条件，因为右下/左上的点均大于或小于该点，不符合条件；故可以选择右上或左下的点，注意边界条件即可。

代码

function Find(target, array)
{
    
    var col = array[0].length;
    var row = array.length;
    
    var j = col - 1;
    var i = 0;
    
    while(i < row && j >= 0) {
        if(array[i][j] < target) {
            i++;
        }else if(array[i][j] == target) {
            return true;
        }else {
            j--;
        }
    }
    return false;
}

运行时间：80毫秒
占用内存：8056k

二维数组中的查找

剑指offer-牛客网

二维数组中的查找

题目描述

思路

代码

最优解题思路

代码

CATALOG

FEATURED TAGS