LeetCode 74.Search a 2D Matrix (搜索二维矩阵)

傷城~ 2022-05-10 08:54 177阅读 0赞

编写一个高效的算法来判断 *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

AC C++ Solution:

可以把矩阵转换为一个排序数组来解决！使用二分查找找到下标，再比较矩阵元素是否为目标值。

/******************************************************
    使用二进制搜索。
    
    n * m矩阵转换为数组=>matrix[x] [y] => a [x * m + y]
    
    数组转换为n * m 矩阵=> a [x] => matrix[x / m] [x％m];
    *******************************************************/
    
    class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target) { 
            if(matrix.empty() || matrix[0].empty())
                return false;
            int n = matrix.size();
            int m = matrix[0].size();
            int l = 0, r = m * n - 1;
    
            while (l != r){
                int mid = (l + r - 1)/2;
                if (matrix[mid / m][mid % m] < target)
                    l = mid + 1;
                else 
                    r = mid;
            }
            return matrix[r / m][r % m] == target;
        }
    };

--------------------

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode:74. Search a 2D Matrix搜索二维矩阵(C语言)

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

快来打我*/ 2022年12月05日 15:26/ 0 赞/ 160 阅读

相关 LeetCode：240. Search a 2D Matrix II搜索二维矩阵 II（C语言）

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

ゞ浴缸里的玫瑰/ 2022年12月05日 15:23/ 0 赞/ 161 阅读

相关 Search a 2D Matrix（C++搜索二维矩阵）

（1）二分法 class Solution { public: bool searchMatrix(vector<vector<int>>&

素颜马尾好姑娘i/ 2022年10月11日 12:13/ 0 赞/ 10 阅读

相关 Search a 2D Matrix II（C++搜索二维矩阵 II）

（1）规划 class Solution { public: bool searchMatrix(vector<vector<int>>

布满荆棘的人生/ 2022年09月06日 14:24/ 0 赞/ 141 阅读

相关 [leetcode]74. Search a 2D Matrix -- JavaScript 代码

这道题很明显的就是用二分法，但是是两个维度的二分法：第一次使用二分法，是要找到那个可能包含target数字的数组。也就是说，这个数组的第一个数应该小于target而它的下

朱雀/ 2022年07月19日 11:52/ 0 赞/ 49 阅读

相关 [leetcode-查找]--74. Search a 2D Matrix

Question 74. Search a 2D Matrix > Write an efficient algorithm that searches for a valu

向右看齐/ 2022年07月12日 03:01/ 0 赞/ 126 阅读

相关 leetcode 74. Search a 2D Matrix 右上角搜索

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix h

朱雀/ 2022年06月08日 01:25/ 0 赞/ 155 阅读

相关 [Leetcode][python]Search a 2D Matrix/搜索二维矩阵

题目大意在一个每行从左到右依次递增，且下一行第一个数字比上一行最后一个数字大的矩阵中，判断目标数字是否存在。解题思路二分搜索：思路1：第一次二分搜索出

墨蓝/ 2022年06月07日 10:52/ 0 赞/ 148 阅读

相关 LeetCode 74.Search a 2D Matrix (搜索二维矩阵)

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

傷城~/ 2022年05月10日 08:54/ 0 赞/ 178 阅读

相关 LeetCode: 240. Search a 2D Matrix II 二维矩阵的搜索

试题 Write an efficient algorithm that searches for a value in an m x n matrix. This mat

怼烎@/ 2021年06月24日 16:11/ 0 赞/ 395 阅读