搜索二维矩阵(二分法)

叁歲伎倆 2022-10-25 15:27 151阅读 0赞

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。  
每行的第一个整数大于前一行的最后一个整数。

class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int n = matrix.size(),m = matrix[0].size();
            int l = 0, r = m*n-1;   //将整个矩阵进行二分
            while(l < r){
                int mid = (l + r) >> 1;;
                if(matrix[mid/m][mid%m] >= target) r = mid;  
                else l = mid + 1;
            }
            return matrix[l/m][l%m] == target;
        }
    };

变体:

*  每行的元素从左到右升序排列。
 *  每列的元素从上到下升序排列。(以右上角为root,把整个矩阵看成一棵二叉搜索树)
 *      class Solution {
        public:
            //二叉搜索树遍历法
            bool searchMatrix(vector<vector<int>>& matrix, int target) {
                int n = matrix.size(),m = matrix[0].size();
                int row = 0,col = m-1;
                while(col >= 0 && row < n){
                    if(matrix[row][col] == target) return true;
                    else if(matrix[row][col] > target) col--;
                    else row++;
                }
                return false;
            }
        };

发表评论取消回复

表情：

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

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

相关阅读

相关 03_搜索二维矩阵 Ⅱ （Python）

目录搜索二维矩阵 II 示例 1：示例 2：提示：解答 1，解法一暴力 2，解法二右上

柔光的暖阳◎/ 2023年01月13日 05:54/ 0 赞/ 73 阅读

相关 LeetCode74. 搜索二维矩阵

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

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

相关搜索二维矩阵(二分法)

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

叁歲伎倆/ 2022年10月25日 15:27/ 0 赞/ 152 阅读

相关 240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。

╰半夏微凉°/ 2022年10月16日 14:22/ 0 赞/ 130 阅读

相关 74. 搜索二维矩阵

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

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

相关 1040 搜索二维矩阵

Description 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性： 1. 每行的元素从左到右

傷城~/ 2022年09月12日 03:49/ 0 赞/ 142 阅读

相关 74. 搜索二维矩阵

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

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

相关 LeetCode 240 搜索二维矩阵

题目：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从

短命女/ 2022年03月16日 12:13/ 0 赞/ 234 阅读

相关 LeetCode 74. 搜索二维矩阵

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

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

相关 LeetCode----------------------搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。

￡神魔★判官ぃ/ 2021年12月10日 12:37/ 0 赞/ 251 阅读