LeetCode热题100 240.搜索二维矩阵||

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

题目描述:

编写一个高效的算法来搜索 m*n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例1:

LeetCode热题100 240.搜索二维矩阵||,LeetCode,leetcode,矩阵,算法

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true

示例 2:

LeetCode热题100 240.搜索二维矩阵||,LeetCode,leetcode,矩阵,算法

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -10^9 <= target <= 10^9

解题思路:

首先最简单的办法就是暴力法直接遍历数组判断target是否出现,时间复杂度为O(mn),没有利用到这个题目矩阵的特点,显然这不是最优解。

根据矩阵 "每行的所有元素从左到右升序排列,每列的所有元素从上到下升序排列"的特点,容易想到可以利用二分法查找每一行或每一列来判断target是否出现,时间复杂度为O(mlogn)或O(nlogm)。

那么还有没有更好的办法呢?

仔细观察示例1中的矩阵,用红线标出每行可能出现target(5)的位置

LeetCode热题100 240.搜索二维矩阵||,LeetCode,leetcode,矩阵,算法

标出示例2矩阵可能出现target(20)的位置

LeetCode热题100 240.搜索二维矩阵||,LeetCode,leetcode,矩阵,算法

可以发现红线把矩阵分隔成了两块区域,左边区域元素都小于target,右边区域元素都大于target,那么不管是左边区域还是右边区域都不可能会出现target,所以只要想办法遍历矩阵红线标记位置,其他位置就不用去遍历。

算法流程:

1.可以选矩阵的一角作为起点,选右上角(0,n-1)为起点开始遍历,元素matrix[i][j]:

  • matrix[i][j]小于target,因为每行元素从左到右是升序,左边元素一定比matrix[i][j]小,所以应该往下搜索,i增加1。
  • matrix[i][j]等于target返回true。
  • matrix[i][j]大于target,因为每列从上到下是升序,下边元素一定比matrix[[i][j]大,所以应该往左搜索,j减少1。

2.若i或j出界,未查找到target,返回false。

以下是算法Java实现:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length;
        int n=matrix[0].length;
        int i=0;
        int j=n-1;
        while(i<m&&j>=0){
            if(matrix[i][j]==target)    return true;
            if(matrix[i][j]>target){
                j--;
            } else{
                i++;
            }
        }
        return false;  
    }
}

以上算法在官方题解中称为"Z字形查找",Z字形查找每次可以排除一行或一列的元素,时间复杂度为O(m+n),空间复杂度为O(1)。

另一种理解方式——二叉搜索树

如下图所示,我们将矩阵逆时针旋转 45° ,并将其转化为图形式,发现其类似于 二叉搜索树 ,即对于每个元素,其左分支元素更小、右分支元素更大。因此,通过从 “根节点” 开始搜索,遇到比 target 大的元素就向左,反之向右,即可找到目标值 target 。

LeetCode热题100 240.搜索二维矩阵||,LeetCode,leetcode,矩阵,算法文章来源地址https://www.toymoban.com/news/detail-737942.html

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

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

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

相关文章

  • 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日
    浏览(57)
  • 【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日
    浏览(36)
  • LeetCode 240. 搜索二维矩阵 II

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 编写一个高效的算法来搜索  m  x  n  矩阵  matrix  中的一个目标值  target  。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例 1: 示例 2: 提示: m == matrix.length n == matrix[i].l

    2024年02月06日
    浏览(43)
  • 算法学习——LeetCode力扣补充篇11(64. 最小路径和、48. 旋转图像 、169. 多数元素、394. 字符串解码、240. 搜索二维矩阵 II )

    64. 最小路径和 - 力扣(LeetCode) 描述 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 示例 1: 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→

    2024年04月23日
    浏览(37)
  • 【leetcode100-021】【矩阵】搜索二维矩阵 II

    【题干】 编写一个高效的算法来搜索  m  x  n  矩阵  matrix  中的一个目标值  target  。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 【思路】 以右上角为起点斜着看这个矩阵,会发现,这是一颗二叉搜索树。 那么我们就从右上角

    2024年02月02日
    浏览(32)
  • 【LeetCode 热题 100】矩阵 专题(大多原地算法,需要一定思维)

    解题思路 在 代码注释中!

    2024年02月15日
    浏览(50)
  • 【算法详解】力扣240.搜索二维矩阵II

    力扣链接:力扣240.搜索二维矩阵II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 题目提到该矩阵是从左到右,从上到下递增的,那么我们就要利用这个性质,从矩阵

    2024年01月21日
    浏览(45)
  • 【LeetCode热题100】【矩阵】螺旋矩阵

    题目链接:54. 螺旋矩阵 - 力扣(LeetCode) 先走外面的圈再走里面的圈,可以用递归来解决,对于要走的一个圈,由四个角决定,其实是三个数,(0,0),(0,n),(m,0),(m,n),每次先从左上角走到右上角,再走到右下角,再走到左下角,再走回来 对于后面两个的往

    2024年04月16日
    浏览(39)
  • 螺旋矩阵 LeetCode热题100

    给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 模拟,朝一个方向走,走过的点标记一下,直到碰到边界或碰到已经走过的路,换个方向。右-下,下-左,左-上,上-右。直到走完所有点。

    2024年02月14日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包