74. 搜索二维矩阵（JS实现）

阳光穿透心脏的1/2处 2023-02-17 12:30 57阅读 0赞

## 1 题目 ##

> 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：  
> 每行中的整数从左到右按升序排列。  
> 每行的第一个整数大于前一行的最后一个整数。  
> 示例 1:  
> 输入:  
> matrix = \[  
> \[1, 3, 5, 7\],  
> \[10, 11, 16, 20\],  
> \[23, 30, 34, 50\]  
> \]  
> target = 3  
> 输出: true  
> 示例 2:  
> 输入:  
> matrix = \[  
> \[1, 3, 5, 7\],  
> \[10, 11, 16, 20\],  
> \[23, 30, 34, 50\]  
> \]  
> target = 13  
> 输出: false

## 2 思路 ##

**这道题就是用二分查找先找到在哪一行，然后在这一行内继续二分查找**

## 3 代码 ##

/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */
    var searchMatrix = function(matrix, target) { 
        let m = matrix.length;
        if (m === 0) return false;
        let n = matrix[0].length;
    
        let low = 0;
        let high = m - 1;
        let mid;
        let row = -1;
    
        while(low <= high) { 
            mid = Math.floor((low + high) / 2);
    
            if (matrix[mid][0] > target) { 
                high = mid - 1;
            } else if (matrix[mid][n - 1] < target) { 
                low = mid + 1;
            } else { 
                row = mid;
                break;
            }
        }
    
        if (row < 0) return false;
    
        low = 0;
        high = n - 1;
    
        while(low <= high) { 
            mid = Math.floor((low + high) / 2);
    
            if (matrix[row][mid] > target) { 
                high = mid - 1;
            } else if (matrix[row][mid] < target) { 
                low = mid + 1;
            } else { 
                return true;
            }
        }
    
        return false;
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关 74. 搜索二维矩阵

编写一个高效的算法来判断 `m x n` 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个

不念不忘少年蓝@/ 2023年10月04日 09:12/ 0 赞/ 102 阅读

相关 leetcode.74:搜索二维矩阵

题目描述：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： ·每行中的整数从左到右按升序排列。

た入场券/ 2023年07月14日 11:00/ 0 赞/ 259 阅读

相关 leetcode 74 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。

你的名字/ 2023年06月16日 01:25/ 0 赞/ 55 阅读

相关 74. 搜索二维矩阵（JS实现）

1 题目 > 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： > 每行中的整数从左到右按升序排列。 > 每行的第一个整数大

阳光穿透心脏的1/2处/ 2023年02月17日 12:30/ 0 赞/ 58 阅读

相关 LeetCode74. 搜索二维矩阵

难度：`中等` 题目描述： > 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： > > 每行中的整数从左到右按升序排列。 >

比眉伴天荒/ 2022年11月15日 03:42/ 0 赞/ 272 阅读

相关 74. 搜索二维矩阵

> 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： > > 每行中的整数从左到右按升序排列。 > 每行的第一个整数大于前一行的最后

偏执的太偏执、/ 2022年10月08日 11:19/ 0 赞/ 248 阅读

相关 74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。

朱雀/ 2022年08月31日 07:17/ 0 赞/ 237 阅读

相关 leetcode:74. 搜索二维矩阵

题目: 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一

淡淡的烟草味﹌/ 2022年03月20日 10:59/ 0 赞/ 450 阅读

相关 LeetCode 74. 搜索二维矩阵

AC1 AC1总是最暴力的 O(n2) class Solution: def searchMatrix(self, matrix, targe

旧城等待，/ 2022年03月14日 12:50/ 0 赞/ 317 阅读

相关 Leetcode 74. 搜索二维矩阵

文章目录 1. 降维后二分查找 1.1 思路 1.2 复杂度 1.3 代码 2. 两次二分查找 2.1 思

快来打我*/ 2021年10月15日 00:53/ 0 赞/ 410 阅读