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

傷城~ 2022-05-10 08:54 201阅读 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 条评论，201人围观）

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

相关阅读

相关 LeetCode | 0240. Search a 2D Matrix II搜索二维矩阵 II【Python】

> LeetCode 0240. Search a 2D Matrix II搜索二维矩阵 II【Medium】【Python】【数组】 Problem [LeetCod

布满荆棘的人生/ 2023年07月16日 03:48/ 0 赞/ 21 阅读

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

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

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

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

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

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

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

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

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

相关 LeetCode74——Search a 2D Matrix

LeetCode74——Search a 2D Matrix 二维数组查找问题，二重循环暴力搜索肯定是超时的，好在二维数组有一定的规律： 1.每一行从左到右是非递减的

拼搏现实的明天。/ 2022年08月10日 06:16/ 0 赞/ 29 阅读

相关 [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 赞/ 141 阅读

相关 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 赞/ 178 阅读

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

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

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

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

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

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

相关 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 赞/ 412 阅读