搜索二维矩阵
   算法    0 comment
搜索二维矩阵
   算法    0 comment

1. 要求

判断在 m * n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:每行中的整数从左到右按升序排,每行的第一个整数大于前一行的最后一个整数。

2. 示例

2.1 正确示例

输入:matrix = [ [1,3,5,7],[10,11,16,20],[23,30,34,60] ], target = 3
输出:true

2.2 错误示例

输入:matrix = [ [1,3,5,7],[10,11,16,20],[23,30,34,60] ], target = 13
输出:false

3. 思路与实现

3.1 解法一

记录每个元素出现的次数。以每个元素值作为key,出现次数作为value,最后匹配与target相等的key,value>=1即返回true。

    function searchMatrix(matrix, target) {
        return matrix.reduce((acc,cur)=>{
            cur.forEach(item =>{
                acc[item] = (acc[item] || 0 ) + 1;
            });
            return acc
        },{})[target] >= 1
    }

3.2 解法二

将后面的数组拼接到前一个数组的尾部,再对拼接后的数组使用二分查找。难点在于确认中点元素所在的行,以及所在该行的位置。示意图:

    function searchMatrix(matrix, target) {
        //矩阵行数和列数
        let row = matrix.length;
        let col = matrix[0].length;
        //开始索引和结束索引
        let start = 0;
        let end = row * col - 1;
        while (start <= end){
            let midIndex = Math.floor((end -start) / 2) + start;
            //先确定中点位置索引所在的行;中点索引midIndex除以每行的长度col的结果向下取整:matrix[Math.floor(midIndex / col)]
            //再确定中点位置索引在该行的位置;中点索引midIndex对每行的长度col取模:midIndex % col
            let midElement = matrix[Math.floor(midIndex / col)][midIndex % col];

            if (target < midElement){
                end--
            }else if (target > midElement){
                start++
            }else{
                return true
            }
        }
        return false
    }
The article has been posted for too long and comments have been automatically closed.