二维数组中的查找

题目描述

示例

代码

代码1 暴力解法，把二维数组遍历一个遍

/*
暴力解法
全遍历一个遍
*/
function Find(target, array)
{
    if(array.length === 0 || array[0].length === 0) return false
    
    for(let i = 0; i < array.length; i++){
        for(let j = 0; j < array[i].length; j++){
            if(array[i][j] === target){
                return true
            }
        }
    }
    
    return false
}

时间复杂度O(n^2)：最坏的情况是遍历一个遍

空间复杂度O(1)

代码2 逐行使用二分查找，时间复杂度O(mlog(N))

/*
逐行使用二分查找
*/
function Find(target, array)
{
    if(array.length === 0 || array[0].length === 0) return false
    
    // 逐行二分查找
    for(let i = 0; i < array.length; i++){
        let flag = binarySearch(array[i], target)
        
        if(flag === true){
            return true
        }
    }
    // 若果没有找到，返回false
    return false
    
    
    function binarySearch(arr, target){
        let left = 0
        let right = arr.length - 1
        
        while(left <= right){
            
            let mid = Math.floor( (left + right)/2 )
            if(arr[mid] === target) return true
            
            if(arr[mid] < target){ // 如果中间的值比目标值小，往右边找
                left = mid + 1
            }else { // 如果中中间的值比目标值大，往左边找
                right = mid - 1
            }
        }
        
        // 如果遍历一个遍了，还是没找到
        return false
    }
}

时间复杂度O(mlog(n))：外层循环最坏会走一个遍m次，内层循环时间复杂度是log(n)，最终时间复杂度O(mlog(n))

空间复杂度O(1)

代码3 利用行列递增的特性，时间复杂度O(m+n)

/*
利用二维数组行列递增特性
主要思路：

由于行列递增，可以得出：
    a.在一列中的某个数字，其上的数字都比它小
    b.在一行中的某个数字，其右的数字都比它大
搜索流程：
    a.首先从数组左下角搜索.
    b.如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。
    c.查找到target,返回true; 如果越界，返回false;
*/
function Find(target, array)
{
    if(array.length === 0 || array[0].length === 0) return false
    
    let row = array.length // 行
    let col = array[0].length // 列
    
    let left = 0
    let down = row - 1
    
    // 从左下角开始找
    // 目标值小，就去上面找，目标值大，就去右面找
    // 找到了就返回true，越界了就返回false
    while(left < col && down >= 0){
        let temp = array[down][left] // 初始值为左下角的数
        
        if(temp === target) return true // 如果相等，返回true
        
        if(temp < target){ // 如果目标值大，向右找
            left++
        }else { // 如果目标值小，向上找
            down--
        }
    }
    
    // 找到下标越界还是没找到，就返回false
    return false
}

时间复杂度O(m+n)：最多找m+n次

空间复杂度O(1)

题目来源

JZ4 二维数组中的查找

参考题解