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.lengthn == matrix[i].length1 <= 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 。

相关文章:
LeetCode热题100 240.搜索二维矩阵||
题目描述: 编写一个高效的算法来搜索 m*n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例1: 输入:matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,2…...
Anaconda安装及使用教程
前言:鉴于本人曾经学过计算机双学位,近日突然发现电脑上装了Anaconda,然而脑子里对为什么装这个,啥时候装的以及怎么用的都忘记了。因此,想学习了解下这个软件。 1 Anaconda简介 Anaconda,一个开源的Pyth…...
动态规划算法实现------转换(编辑、变换)问题
目录 一、字符串转换问题 1.1问题 1.2确定动态规则(DP、状态转移方程)、初始值 (1)插入操作实现状态转移 (2)删除操作实现状态转移 (3)替换操作实现状态转移 (4)初始值 1.3动态规划算法代码实现 (1)完整代码 (2)程序速度优化 二、矩阵变换问题 2.1问题 2.2矩阵乘法 (1)矩阵相乘…...
C#使用Oracle.ManagedDataAccess.dll
1、添加引用 在网上下载一个Oracle.ManagedDataAccess.dll,引用即可,视操作系统的位数,最重要的是减少了Oracle客户端的安装; 2、web.config字串 <appSettings> <add key"hrp" value"Data Source (…...
分享88个工作总结PPT,总有一款适合您
分享88个工作总结PPT,总有一款适合您 88个工作总结PPT下载链接:https://pan.baidu.com/s/1y08X9RMdIOCncbs28aMgDw?pwd8888 提取码:8888 Python采集代码下载链接:采集代码.zip - 蓝奏云 蓝色水彩风年终总结PPT模板 清新水彩简…...
【华为OD题库-002】最佳植树距离-Java
题目 小明在直线的公路上种树,现在给定可以种树的坑位的数星和位置,以及需要种多少棵树苗,问树苗之间的最小间距是多少时,可以保证种的最均匀(两棵树苗之间的最小间距最大) 输入描述 输入三行: 第一行一个整数:坑位的数…...
【python与数据结构】(leetcode算法预备知识)
笔记为自我总结整理的学习笔记,若有错误欢迎指出哟~ python与数据结构 Python 中常见的数据类型数据结构1.数组(Array)2.链表(Linked List)3.哈希表(Hash Table)4.队列(Queue&#x…...
前端+Python实现Live2D虚拟直播姬
写在前面 很早就在b站上看到有虚拟主播的方案,之前看到的方案主要分为3种: ①用的unity+live2d②有的用的steam的Vtube Studio这款软件③也有基于galgame的。基于纯前端和python的我好像没找到,在掘金看到一篇文章:juejin.cn/post/720474… ,使用的pixi-live2d-display这…...
华纳云 宝塔怎么配置香港服务器多ip?
宝塔面板是一款开源的服务器管理面板,提供了简单易用的图形化界面,使用户能够轻松管理和配置服务器。通过切换到香港服务器多IP,用户可以拥有更多的IP资源,提供更灵活的网络服务。 配置香港服务器多IP 1.登录宝塔面板 打开浏览器&…...
云计算是什么
一文读懂云计算:发展历程、概念技术与现状分析 - 知乎 “现阶段所说的云计算,已经不单单是一种分布式计算,而是分布式计算、效用计算、负载均衡、并行计算、网络存储、热备份冗杂和虚拟化等计算机技术混合演进并跃升的结果。” 云计算的关键…...
【POI-EXCEL-下拉框】POI导出excel下拉框数据太多导致下拉框不显示BUG修复
RT 最近在线上遇到一个很难受的BUG,我一度以为是我代码逻辑出了问题,用了Arthas定位分析之后,开始坚定了信心:大概率是POI的API有问题,比如写入数据过多。 PS:上图为正常的下拉框。但是,当下拉…...
【ES专题】ElasticSearch 高级查询语法Query DSL实战
目录 前言阅读对象阅读导航前置知识数据准备笔记正文一、ES高级查询Query DSL1.1 基本介绍1.2 简单查询之——match-all(匹配所有)1.2.1 返回源数据_source1.2.2 返回指定条数size1.2.3 分页查询from&size1.2.4 指定字段排序sort 1.3 简单查询之——…...
陕西某小型水库雨水情测报及大坝安全监测项目案例
项目背景 根据《陕西省小型病险水库除险加固项目管理办法》、《陕西省小型水库雨水情测报和大坝安全监测设施建设与运行管理办法》的要求,为保障水库安全运行,对全省小型病险水库除险加固,建设完善雨水情测报、监测预警、防汛道路、通讯设备、…...
pte rs练习方法 请介绍一下crank请介绍一下sanctuary请介绍一下solitary请介绍一下coarse请介绍一下deception
目录 pte rs练习方法 请介绍一下crank 请介绍一下sanctuary 请介绍一下solitary 请介绍一下coarse 请介绍一下deception pte rs练习方法 请介绍一下crank “Crank”一词可以个指不同的事物,具体含义视上下文而定。在不同的领域,这个词有不同的解…...
NLP之LSTM与BiLSTM
文章目录 代码展示代码解读双向LSTM介绍(BiLSTM) 代码展示 import pandas as pd import tensorflow as tf tf.random.set_seed(1) df pd.read_csv("../data/Clothing Reviews.csv") print(df.info())df[Review Text] df[Review Text].astyp…...
【实现多个接口的使用】
文章目录 前言实现多个接口接口间的继承接口使用实例给对象数组排序创建一个比较器 总结 前言 实现多个接口 Java中不支持多继承,但是一个类可以实现多个接口 下面是自己反复理了很久才敲出来的,涉及到之前学的很多知识点 如果哪看不懂,真…...
Mac收集的几个终端命令
文章目录 转UTF-8编码格式打tag 包 命令:压缩加密文件显示隐藏文件取消Mac电脑安全模式 转UTF-8编码格式 cd到目录下 iconv -f gbk -t utf-8 gbk.txt > utf8.txt打tag 包 命令: cd到目录下 tar -cvf demo.tar.gz demo a demo压缩加密文件 cd 到文…...
206. 反转链表、Leetcode的Python实现
博客主页:🏆看看是李XX还是李歘歘 🏆 🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺 💗点关注不迷路,总有一些📖知识点📖是你想要的💗 ⛽️今…...
VS2022 打包WPF安装程序最新教程(图文详解)
文章目录 前言一、安装打包Installer插件1、单独安装2、VS中在线安装二、使用步骤1、创建安装项目2、安装项目主界面3、添加项目输出4、添加快捷方式图标5、添加卸载项目a、新建项目b、添加项目输出c、创建快捷方式6、给快捷方式添加图标a、在Resource文件夹中添加图标文件b、选…...
清华大模型GLM
2022年,清华大学发布了一款具有重要意义的 GLM 大模型,它不仅在中文语言处理方面取得了显著的进展,还在英文语言处理方面表现出了强大的能力。GLM大模型区别于OpenAI GPT在线大模型只能通过API方式获取在线支持的窘境,GLM大模型属于开源大模型,可以本地部署进行行业微调、…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...


