当前位置: 首页 > news >正文

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

题目描述:

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

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

示例1:

输入: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:

输入: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)的位置

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

可以发现红线把矩阵分隔成了两块区域,左边区域元素都小于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 。

http://www.lryc.cn/news/215265.html

相关文章:

  • Anaconda安装及使用教程
  • 动态规划算法实现------转换(编辑、变换)问题
  • C#使用Oracle.ManagedDataAccess.dll
  • 分享88个工作总结PPT,总有一款适合您
  • 【华为OD题库-002】最佳植树距离-Java
  • 【python与数据结构】(leetcode算法预备知识)
  • 前端+Python实现Live2D虚拟直播姬
  • 华纳云 宝塔怎么配置香港服务器多ip?
  • 云计算是什么
  • 【POI-EXCEL-下拉框】POI导出excel下拉框数据太多导致下拉框不显示BUG修复
  • 【ES专题】ElasticSearch 高级查询语法Query DSL实战
  • 陕西某小型水库雨水情测报及大坝安全监测项目案例
  • pte rs练习方法 请介绍一下crank请介绍一下sanctuary请介绍一下solitary请介绍一下coarse请介绍一下deception
  • NLP之LSTM与BiLSTM
  • 【实现多个接口的使用】
  • Mac收集的几个终端命令
  • 206. 反转链表、Leetcode的Python实现
  • VS2022 打包WPF安装程序最新教程(图文详解)
  • 清华大模型GLM
  • 实时数仓-hologres使用总结
  • 博客摘录「 TCP/IP网络编程——习题答案」2023年10月29日
  • MySQL数据库干货_13—— MySQL查询数据
  • Docker Consul概述及构建
  • 《Linux从练气到飞升》No.25 Linux中多线程概念
  • 2021~2023年度长垣起重机博览会最佳产品彩页(修订中)
  • OpenCV标定演示,及如何生成标定板图片
  • python venv 虚拟环境使用
  • useCallback和useMemo的区别?
  • Angular组件生命周期详解
  • Redsync 多 Redis 实例使用 demo