【LeetCode】74. 搜索二维矩阵

这篇具有很好参考价值的文章主要介绍了【LeetCode】74. 搜索二维矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

74. 搜索二维矩阵(中等)

【LeetCode】74. 搜索二维矩阵,LeetCode刷题,leetcode,矩阵,算法
【LeetCode】74. 搜索二维矩阵,LeetCode刷题,leetcode,矩阵,算法【LeetCode】74. 搜索二维矩阵,LeetCode刷题,leetcode,矩阵,算法
【LeetCode】74. 搜索二维矩阵,LeetCode刷题,leetcode,矩阵,算法

方法一:二分查找

思路

  • 总体思路

    由于二维矩阵固定列的「从上到下」或者固定行的「从左到右」都是升序
    因此我们可以使用两次二分来定位到目标位置。

    1. 第一次二分: 从第 0 列中的「所有行」开始找,找到合适的行 row, 即找到最后一个满足 matrix[x][0] <= target 的行号;
    2. 第二次二分:从 row 中「所有列」开始找,找到合适的列 col ,即找到最后一个满足 matrix[row][y] <= target 的列号。
  • 二分代码解释

    这里用到了二分查找的高级模板,left = mid,用于查找数组中当前索引及其直接左邻居索引的元素或条件。

    注意,while 语句的条件是 left < right

    此外,mid 值计算需要 +1 ,如果不加 1 会出现死循环(比如l = 2, r = 3 的时候,如果不加 1,在满足 l = mid 的情况下,会一直死循环)。

    int binarySearch(vector<int>& nums, int target){
    	  if(nums.size() == 0)
    	  	return -1;
    
     	 int left = 0, right = nums.size();
      		while(left < right){
    	    // Prevent (left + right) overflow
    	    int mid = left + (right - left) / 2;
    	    if(nums[mid] == target){ return mid; }
    	    else if(nums[mid] <= target) { left = mid; }
    	    else { right = mid + 1; }
    	  }
    
    	  // Post-processing:
    	  // End Condition: left == right
    	  if(left != nums.size() && nums[right] == target) return right;
    	  return -1;
    	}
    

代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int row, col;
        int left = 0, right = m-1;
        // 第一次二分找到最后一个不大于目标值的元素的所在行
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(matrix[mid][0] <= target)  left = mid;
            else right = mid - 1;
        }
        row = right;

        // 可以先判断,减少时间复杂度
        if(matrix[row][0] == target) return true;
        if(matrix[row][0] > target) return false;

        // 第二次二分找到所在列
        left = 0, right = n-1;
        while(left<right){
            int mid = left + (right - left + 1) / 2;
            if(matrix[row][mid] <= target)   left = mid;
            else right = mid - 1;
        }
        col = right;
        return matrix[row][col] == target;
    }
};

方法二:一次二分

思路

  • 如果将数组按行逐元素连接起来,那么数组将形成一个单调递增序列,我们可以使用一次二分在该 “一维数组” 中查找,如果找到target ,返回 true;否则返回false。
  • 对于一次二分,因为只有找到 target 和 没找到 target 两种情况,所以只需要普通的模板。

代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n - 1;
        // 一次二分
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(matrix[mid/n][mid%n] == target) return true;
            else if(matrix[mid/n][mid%n] < target) left = mid + 1;
            else right = mid - 1;             
        }
        return false;
    }
};

方法三:抽象二叉搜索树

思路

  • 我们可以将二维矩阵抽象成「以右上角为根的 BST」:
    【LeetCode】74. 搜索二维矩阵,LeetCode刷题,leetcode,矩阵,算法

  • 那么我们可以从根(右上角)开始搜索,如果当前的节点不等于目标值,可以按照树的搜索顺序进行:

    • 当前节点「大于」目标值,搜索当前节点的「左子树」,也就是当前矩阵位置的「左方格子」,即 y–
    • 当前节点「小于」目标值,搜索当前节点的「右子树」,也就是当前矩阵位置的「下方格子」,即 x++

代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        // 当前的坐标值,从右上角开始查找
        int x = 0, y = n-1;

        while(check(x, y, m, n) && matrix[x][y] != target){
            // 如果matrix[x][y] > target 说明需要向左查找
            if(matrix[x][y] > target)   y--;
            // 如果matrix[x][y] > target 说明需要向下查找
            else if(matrix[x][y] < target)  x++;
        }
        
        return check(x, y, m, n) && matrix[x][y] == target;
    }
    // 边界情况判断
    bool check(int x, int y, int m, int n){
        return x>=0 && x<m && y>=0 && y<n;
    }
};

参考资料

  1. 二分查找的三种模板(C++版)

  2. 【宫水三叶】一题双解:「二分」&「抽象 BST」解法文章来源地址https://www.toymoban.com/news/detail-700360.html

到了这里,关于【LeetCode】74. 搜索二维矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode热题100】--74.搜索二维矩阵

    按行搜索,使用二分查找

    2024年02月02日
    浏览(43)
  • leetcode 74. 搜索二维矩阵(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/search-a-2d-matrix 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回

    2024年02月16日
    浏览(43)
  • LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 示例 1: 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]],

    2024年04月14日
    浏览(42)
  • leetcode做题笔记74搜索二维矩阵

    给你一个满足下述两条属性的  m x n  整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数  target  ,如果  target  在矩阵中,返回  true  ;否则,返回  false  。 本题可直接遍历整个矩阵进行查找 本题考察矩

    2024年02月13日
    浏览(44)
  • LeetCode 热题 100 JavaScript -- 74. 搜索二维矩阵

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。

    2024年02月13日
    浏览(39)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(56)
  • leetcode(矩阵)74. 搜索二维矩阵(C++详细解释)DAY7

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 m == matrix.length n == matrix[i].length 1 = m, n = 100 -10^ 4 = matrix

    2024年02月19日
    浏览(35)
  • LeetCode74.Search-A-2d-Matrix<搜索二维矩阵>

    题目:   思路: 矩阵,搜索数是否在矩阵内。那就查找他是否在每一行中。如果符合这一行的范围,那就一直找这一列是否存在,如果存在返回true;否则false;  

    2024年02月16日
    浏览(48)
  • 【LeetCode】240.搜索二维矩阵Ⅱ

    编写一个高效的算法来搜索  m  x  n  矩阵  matrix  中的一个目标值  target  。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例 1: 示例 2: 提示: m == matrix.length n == matrix[i].length 1 = n, m = 300 -10^9 = matrix[i][j] = 10^9 每行的所有元素

    2024年02月12日
    浏览(34)
  • leetcode—搜索二维矩阵II

    编写一个高效的算法来搜索  m  x  n  矩阵  matrix  中的一个目标值  target  。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例 1: 暴力求解 对矩阵的每一行采用二分查找进行查找 Z字型查找 从矩阵的右上角(0,n-1)进行搜索 具

    2024年01月17日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包