2023-8-23

8-23

数组

题号剑指 Offer 04. 二维数组中的查找

题目 在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解法一：暴力解法



function findNumberIn2DArray(matrix: number[][], target: number): boolean {

    for(let n =0 ;n<matrix.length;n++){
        for(let m = 0;m<matrix[n].length;m++)
        {   
           if(matrix[n][m]===target)return true
        }
    }
    return false
};

解法二：

由于 每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。所以可以对每一行都进行一次二分查找



function findNumberIn2DArray(matrix: number[][], target: number): boolean {
    for(const row of matrix){
        const index = search(row,target)
        if(index>=0){
            return true
        }
    }
    return false
};

const search = (nums:number[],target:number):number=>{
    let low = 0,high = nums.length-1
    while(low<=high){
        const mid = Math.floor((high-low)/2)+low
        const num = nums[mid]
        if(num===target){
            return mid
        }
        else if(num>target){
            high =mid-1
        }
        else{
            low = mid+1
        }
    }
    return -1
}

解法三：由于 每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序，旋转45度后可以抽象成一棵二叉搜索树

function findNumberIn2DArray(matrix: number[][], target: number): boolean {
    let n = matrix.length-1
    let m = 0
    while(n>=0&&m<matrix[0].length){
        if(target>matrix[n][m]){m++}
        else if(target<matrix[n][m]){n--}
        else {return true}
    }
return false
};

//感觉其实可以理解为左下角的数是该行的最小值，该列的最大值。所以如果target比左下角还小，则肯定比这一行都小，所以可以上移一行寻找；如果target比左下角还大，则肯定比这一列都大，所以可以右移一列寻找