首页/新闻资讯/正文详情

LeetCode 240. 搜索二维矩阵 II:从右上角开始的巧妙搜索

发布时间:2026/11/12 22:41:18 来源:云帆数科 栏目:资讯中心
LeetCode 240. 搜索二维矩阵 II:从右上角开始的巧妙搜索
问题描述给定一个m x 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算法思路从右上角出发暴力遍历整个矩阵需要 O(m * n) 的时间复杂度。利用矩阵的排序特性我们可以从矩阵的右上角或左下角开始搜索实现线性时间的查找。核心思想初始化指针在右上角(row0, coln-1)。将当前指针指向的值cur与目标值target比较如果cur target查找成功返回true。如果cur target说明当前值太大而同一列下方的值都更大因此不可能在当前列找到目标。将指针向左移动一列(col--)。如果cur target说明当前值太小而同一行左边的值都更小因此不可能在当前行找到目标。将指针向下移动一行(row)。重复步骤2直到找到目标或指针移出矩阵边界row m或col 0。若移出边界则说明矩阵中不存在目标值返回false。这种方法每一步都排除掉一行或一列因此最多走m n步时间复杂度为O(m n)空间复杂度为O(1)。代码实现以下是该算法的 Java 实现classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){intmmatrix.length;intnmatrix[0].length;// 从右上角开始introw0;intcoln-1;while(rowmcol0){intcurmatrix[row][col];// 找到了if(curtarget){returntrue;}// 当前值太大往左走elseif(curtarget){col--;}// 当前值太小往下走else{row;}}returnfalse;}}图解算法流程为了更直观地理解搜索路径下图展示了在一个 5x5 矩阵中查找目标值5的过程。指针从右上角(0,4)开始根据比较结果逐步向左或向下移动最终在(1,1)位置找到目标。(上图展示了从右上角开始的搜索路径红色箭头表示移动方向绿色单元格表示找到目标)复杂度分析时间复杂度O(m n)。最坏情况下指针从右上角移动到左下角总共移动m n步。空间复杂度O(1)。只使用了几个整型变量。总结从右上角或左下角开始的“步进法”是解决此类行列均有序矩阵搜索问题的经典且高效的方法。它巧妙地利用了排序特性每次比较都能排除一整行或一整列将搜索复杂度从二次降为线性。掌握这种思路对于解决类似的二维搜索问题大有裨益。在后续章节中我们可以探讨此算法的变种、与其他解法如二分查找的比较以及在实际项目中的应用场景。

相关推荐

Docker中Jenkins密码重置的3种实用方案
Docker中Jenkins密码重置的3种实用方案

1. 项目背景与需求解析在Docker Desktop环境中运行的Jenkins服务,密码管理是个看似简单却经常让开发者头疼的问题。上周我在本地开发环境就遇到了这个场景:新接手一个遗留项目,发现前任同事留下的Jenkins实例密码已经失效,而容器内… · 2026/9/16 15:27:51

Linux企业级应用的核心优势与实战解析
Linux企业级应用的核心优势与实战解析

1. Linux在企业级应用中的核心优势Linux作为开源操作系统的代表,在企业级应用中展现出独特的价值主张。从技术架构角度看,Linux采用模块化设计,内核仅提供基础功能,其他组件通过用户空间程序实现。这种设计使得系统维护和更新可以… · 2026/8/3 17:11:00

基于 Grok-4.5 的 X-Dynosaur 签名算法纯算还原分析
基于 Grok-4.5 的 X-Dynosaur 签名算法纯算还原分析

基于 Grok-4.5 的 X-Dynosaur 签名算法纯算还原分析 版本基准:webmssdk 2.0.0.507(sdkVersion5.3.0, scmVersion2.0.0.507) 形态特征:挂载于 URL Query 上的约 392 字符签名参数,通常与 X-Gnarly / X-Bogus 配合出现。… · 2026/10/16 7:48:29

原州区考电工证多少钱电子证书查询
原州区考电工证多少钱电子证书查询

原州区考电工证多少钱电子证书查询 之前考的证在外省能不能转过来?这是很多学员问得最多的问题。特别是那些已经在外地工作,但想回到原州区发展的朋友,证书的 电子证书… · 2026/11/12 22:40:21

宁远县电工证培训多少钱?证书过期了不知道怎么复审延期
宁远县电工证培训多少钱?证书过期了不知道怎么复审延期

宁远县电工证培训多少钱?证书过期了不知道怎么复审延期 证书过期了不知道怎么复审延期?别急,这可能是你最头疼的问题之一。特别是在宁远县,电工证作为特种作业证之一,其有效期、复审流程和培训价格都是从业者关注的重点。本文就来聊聊宁远县电工证培训的… · 2026/11/12 22:40:21

特种作业和爆破工千万别踩坑:学历不高也能报上名?
特种作业和爆破工千万别踩坑:学历不高也能报上名?

特种作业和爆破工千万别踩坑:学历不高也能报上名? 学历不高怕报不上名?特种作业和爆破工报考其实没有那么难,关键是你有没有踩到那些隐藏的坑。特别是像南阳卧龙区这样的地方,从事公路工程的小伙伴,很多都是一线作业人员,但很多人因为学历问题不敢尝试… · 2026/11/12 22:40:21

2026河南最新政策:需要考电工证的资料怎么准备才不被坑?
2026河南最新政策:需要考电工证的资料怎么准备才不被坑?

2026河南最新政策:需要考电工证的资料怎么准备才不被坑? 你是不是也像我一样,刚开始接触电工证考试,满脑子都是“不知道去哪报名怕被中介坑”?特别是2026年河南最新政策出来后,很多人都在问:… · 2026/11/12 22:40:21

电工证怎么查编号 通过率揭秘:特种电工持证人的薪资前景与职业发展路径
电工证怎么查编号 通过率揭秘:特种电工持证人的薪资前景与职业发展路径

电工证怎么查编号 通过率揭秘:特种电工持证人的薪资前景与职业发展路径 证书过期了不知道怎么复审延期?别慌,很多人在实际工作中都遇到过类似情况,尤其是从事特种作业的电工。 电工证怎么查编号… · 2026/11/12 22:40:21

电工证不用会作废么?值不值得考?三门峡电工从业者必看
电工证不用会作废么?值不值得考?三门峡电工从业者必看

电工证不用会作废么?值不值得考?三门峡电工从业者必看 证书过期了不知道怎么复审延期,这是很多特种作业操作证持证人的真实痛点。尤其是像电工证这种高需求的证书,一旦过期,不仅影响工作,还可能影响职业发展。那么,… · 2026/11/12 22:39:21

电工证丢失还能补吗?千万别踩坑,丢了证等于失业
电工证丢失还能补吗?千万别踩坑,丢了证等于失业

电工证丢失还能补吗?千万别踩坑,丢了证等于失业 你正在找工作,但手里的电工证突然丢了,这下怎么办?别急,先别慌, 电工证丢失还能补吗 ?答案是肯定的,但 千万别踩坑 ,补办流程如果不了解,可能会耽误你上岗、甚至影响到你的收入。… · 2026/11/12 14:09:01

电力电缆作业证直播报名入口与办理流程良心建议
电力电缆作业证直播报名入口与办理流程良心建议

电力电缆作业证直播报名入口与办理流程良心建议 你是不是也担心学历不高报不了名?别急,今天就给你讲讲 电力电缆作业证直播 的报名流程和那些你必须知道的干货, 良心建议 在这里,别错过。 电力电缆作业证直播报名需要什么条件?… · 2026/11/11 19:07:25

英德电工证报考费多少钱,怕考不过白交培训费?看完这篇别再踩坑
英德电工证报考费多少钱,怕考不过白交培训费?看完这篇别再踩坑

英德电工证报考费多少钱,怕考不过白交培训费?看完这篇别再踩坑 怕考不过白交培训费?英德电工证报考费多少钱,你真的了解吗?现在市面上培训机构五花八门,价格参差不齐,很多人一不小心就花了冤枉钱,结果还考不过。别急,今天就来给你说清楚英德电工证的… · 2026/11/11 17:14:54

电工证设年审有效期多久官方回应来了,工地太忙根本没时间复习考试
电工证设年审有效期多久官方回应来了,工地太忙根本没时间复习考试

电工证设年审有效期多久官方回应来了,工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,这是很多一线电工、焊工、高处作业人员的真实写照。尤其是像你这样刚毕业的鹤壁工程类毕业生,一边要找工作,一边要考证,时间紧张,复习效率低。但你可能不知… · 2026/11/12 0:00:56

新乡电工证实操怕挂科?电工作业动漫图+报考避坑全解析
新乡电工证实操怕挂科?电工作业动漫图+报考避坑全解析

新乡电工证实操怕挂科?电工作业动漫图+报考避坑全解析 实操考试心里没底怕挂科?你不是一个人。新乡的水利工程从业者,很多在报考电工证的时候都担心自己操作不熟练、考试不通过, 千万别踩坑 ,选对资料和方法真的能提高通过率。… · 2026/11/12 0:00:56

网电工证千万别踩坑:实操考试心里没底怕挂科怎么破?
网电工证千万别踩坑:实操考试心里没底怕挂科怎么破?

网电工证千万别踩坑:实操考试心里没底怕挂科怎么破? 实操考试心里没底怕挂科,这是很多准备报考【网电工证】的学员最真实的感受。尤其是在高压电工、低压电工等工种上,操作环节的容错率极低,一旦失误就可能直接被判定不合格。很多人因为担心挂科而放弃考… · 2026/11/12 0:00:56

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/12 4:35:34

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/12 4:36:01

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/12 21:15:21

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码