LeetCode 74:搜索二维矩阵——Java 虚拟一维数组与二分查找详解

发布时间:2026/9/30 8:02:11

LeetCode 74:搜索二维矩阵——Java 虚拟一维数组与二分查找详解 一、题目描述给定一个m × n的整数矩阵matrix矩阵具有以下两个特点每一行中的整数从左到右按非严格递增顺序排列每一行的第一个整数都大于前一行的最后一个整数。再给定一个整数target如果它存在于矩阵中就返回true否则返回false。例如matrix [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] target 3数字3位于第一行第二列因此返回true。如果target 13矩阵中不存在该数字则返回false。看到“有序”和“查找”这两个关键词应该优先想到二分查找。本题的关键在于如何在不创建额外数组的情况下对二维矩阵进行一次二分查找。二、为什么可以把矩阵看成一维数组先观察题目给出的矩阵1 3 5 7 10 11 16 20 23 30 34 60每一行内部都是升序的并且下一行的第一个数字大于上一行的最后一个数字。因此如果按照从左到右、从上到下的顺序展开可以得到[1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]这个一维数组仍然保持整体升序所以可以直接使用二分查找。最直观的做法是创建一个新数组将矩阵中的所有元素复制进去再对新数组进行搜索。但这会额外占用O(mn)的空间而且复制数据本身也需要O(mn)的时间。实际上我们不需要真正展开矩阵。只要能够把一维数组的下标映射回矩阵中的行和列就可以把原矩阵当成一个“虚拟的一维数组”。三、一维下标如何映射到二维坐标假设矩阵有n列。一维数组中的每n个元素对应二维矩阵中的一整行。如果一个元素在虚拟一维数组中的下标为i那么它在二维矩阵中的坐标为行号 i / n 列号 i % n这里使用的都是整数运算。以三行四列的矩阵为例n 4一维下标1行号为1 / 4 0列号为1 % 4 1对应matrix[0][1] 3一维下标6行号为6 / 4 1列号为6 % 4 2对应matrix[1][2] 16一维下标9行号为9 / 4 2列号为9 % 4 1对应matrix[2][1] 30。因此在二分查找中得到中间下标mid后可以直接通过下面的代码访问对应元素int num matrix[mid / n][mid % n];这就是本题最核心的下标映射关系。可以简单记忆为除以列数得到行模上列数得到列。四、确定二分查找的边界矩阵一共有m行、n列因此元素总数是m × n。如果按照虚拟一维数组处理其下标范围就是0 m × n - 1所以二分查找的左右边界为int left 0; int right m * n - 1;这里采用闭区间[left, right]。只要left right区间内就仍然存在尚未检查的元素while (left right) { // 二分查找 }为了避免直接计算(left right) / 2时发生整数溢出可以写成int mid left ((right - left) 1);在本题的数据范围内截图中的(left right) 1通常也能通过。但从通用二分查找模板来看先计算right - left更稳妥。五、如何更新左右边界通过映射关系取得中间元素后将它与target比较int num matrix[mid / n][mid % n];接下来有三种情况。1. 中间元素等于目标值if (num target) { return true; }说明已经找到目标值可以直接结束搜索。2. 中间元素小于目标值if (num target) { left mid 1; }因为虚拟数组整体有序所以mid及其左侧的元素都不可能等于target下一轮只需要搜索右半部分。3. 中间元素大于目标值else { right mid - 1; }此时mid及其右侧的元素都可以排除下一轮只搜索左半部分。如果循环结束后仍未返回true说明目标值不存在最终返回false。六、完整 Java 代码class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m matrix.length; // 行数 int n matrix[0].length; // 列数 // 将二维矩阵视为一个虚拟的一维有序数组 int left 0; int right m * n - 1; while (left right) { // 计算虚拟一维数组的中间下标 int mid left ((right - left) 1); // 将一维下标映射回二维矩阵坐标 int num matrix[mid / n][mid % n]; if (num target) { return true; } if (num target) { left mid 1; } else { right mid - 1; } } return false; } }这段代码没有真正创建一维数组只是在逻辑上将二维矩阵展开。二分查找使用的是虚拟下标只有访问元素时才通过除法和取模转换为二维坐标。七、示例推演仍以如下输入为例matrix [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60] ] target 3矩阵共有3 × 4 12个元素因此初始搜索区间为[0, 11]。第一次查找mid 5 row 5 / 4 1 col 5 % 4 1 num matrix[1][1] 11因为11 3所以令right 4。第二次查找mid 2 row 2 / 4 0 col 2 % 4 2 num matrix[0][2] 5因为5 3所以令right 1。第三次查找mid 0 num matrix[0][0] 1因为1 3所以令left 1。第四次查找mid 1 num matrix[0][1] 3中间元素等于目标值返回true。八、复杂度分析矩阵中共有m × n个元素二分查找每次都将搜索范围缩小一半因此时间复杂度为O(log(m × n))算法只使用了几个变量没有创建真正的一维数组因此空间复杂度为O(1)九、常见错误1. 使用mid / m计算行号映射时应该除以列数n因为一维数组中每连续n个元素构成一行。正确写法是matrix[mid / n][mid % n]2. 将右边界写成m * n一共有m × n个元素但最后一个下标是m × n - 1。闭区间写法中右边界应为int right m * n - 1;3. 更新边界时没有跳过mid如果写成left mid或right mid在某些情况下区间无法继续缩小可能造成死循环。闭区间模板应使用mid 1和mid - 1。4. 忽略矩阵整体有序的前提这种虚拟展开后二分查找的方法成立是因为下一行首元素大于上一行尾元素。如果只保证每行有序而不能保证行与行之间整体有序就不能直接使用本方法。5. 真的创建一维数组创建数组虽然也能完成搜索但会带来O(mn)的复制时间和额外空间失去了虚拟映射的优势。十、总结这道题本质上仍然是一道标准二分查找题。矩阵看起来是二维结构但题目给出的两条有序条件保证了它按行展开后是一个完整的升序数组。我们不需要真正展开矩阵只需在[0, m × n - 1]范围内进行二分查找。当得到一维下标mid后利用mid / n找到行号利用mid % n找到列号再访问对应的矩阵元素。
延伸阅读

更多相关文章

2026/9/30 8:01:14

深度解析怀化市建设局网站功能与价值:打造阳光透明、便民高效的数字化政务新窗口

在这个数字化浪潮汹涌的时代,我们每一个人都在经历着生活方式的深刻变革。从移动支付到在线教育,从在线挂号到政务服务“一网通办”,科技的触角已经延伸到了生活的每一个角落。而对于我们这些生活在怀化这座山城里的人来说,有一个网站的身影显得尤为独特且重要,那就是怀化…

2026/9/30 8:01:38

高通跃龙IQ-9075平台的开发记录(3): AI部署的SDK选择

设备: 高通跃龙 IQ-9075 EVK(SA8775P,Hexagon v73) 运行时: Qualcomm Genie(QAIRT 2.42 附带示例源码 / 设备侧 Genie 1.14.0) 模型: Qwen2.5-7B-Instruct(本地编译) 依据: Qualcomm AI Hub Mod…

2026/9/29 4:28:13

2026年中最新指南:8款免费好用的AI写小说工具真实测评

是不是很多写小说的小伙伴,总感觉码字效率提不上来?萌新入坑最头疼的,就是不会搭建完整小说大纲、找不到贴合剧情的优质小说的素材,写着写着就卡文停更。不少人跟风乱找AI写小说工具,到头来却白白浪费时间。 作为常年…

2026/9/30 8:01:48

科研绘图效率利器:从素材库到Cell级论文配图的完整指南

上周刚帮实验室一个师弟改完机制图,他把线粒体画成了椭圆加波浪线,细胞核用矩形加几个点,流速箭头大小完全不统一,一眼看上去像三种风格硬拼在一起。我花了两个小时把它们全部替换成BioRender的标准图标,整套图立刻就不…

2026/9/30 8:01:48

Windows窗口置顶工具:原理、快捷键与脚本实战

上班的时候桌面上摊着三四个窗口是常态:左边挂着需求文档,右边是编辑器,后台还有一个不停刷日志的终端。想对着文档抄一段参数,手一抖切到别的窗口,文档就沉到后面去了,还得回任务栏把它捞出来。这种来回折…

2026/9/30 7:56:47

Linux软链接与硬链接的本质区别及实战应用

1. 为什么软链接和硬链接不是“差不多就行”的替代品?在Linux系统里,软链接(symbolic link)和硬链接(hard link)常被新手统称为“快捷方式”,但这种类比会埋下严重隐患。我刚入行时就吃过亏&…

2026/9/29 11:07:23

东莞市品牌网站建设报价常见报错与解决

东莞品牌网站建设报价单背后:一份保姆级建站教程避坑实录 网站做好了没人访问,这大概是很多老板最头疼的事。花了大几万做的品牌站,上线后流量惨淡,比路边摊还冷清。别急着骂外包公司,很多“东莞品牌网站建设报价”里藏着不少猫腻,比如用模板站冒充定制…

2026/9/29 21:48:03

如何划分训练/验证集:Spirula Studio五种eval_mode策略详解

如何划分训练/验证集:Spirula Studio五种eval_mode策略详解 【免费下载链接】spirula-studio Cross-vendor 3D Gaussian Splatting trainer - video to splat to mesh, Vulkan or CUDA. 项目地址: https://gitcode.com/GitHub_Trending/sp/spirula-studio Sp…

2026/9/29 7:00:49

SEO怎么推广速查手册新手避坑实战指南

SEO怎么推广速查手册新手避坑实战指南 模板网站太丑不够用?别急着加滤镜,那是治标不治本。很多老板盯着后台流量掉得眼红,却还在纠结首页Banner的圆角是不是3像素。这就像穿着西装去挖土,姿势不对,努力白费。我整理这份 速查手册…

2026/9/30 0:01:22

MATLAB+Yalmip+CPLEX实战:综合能源系统优化调度全流程解析

做综合能源系统优化调度这活儿,最痛苦的不是建模本身,而是模型写完之后不知道该怎么求解。看论文里轻飘飘一句“采用Yalmip调用CPLEX求解”,自己上手时却往往卡在环境配置、变量声明、约束写法和求解状态判读上,一耗就是两三天。这…

2026/9/30 0:01:22

I3C比I2C快10倍?RK3576实战:速率、DTS配置与混合总线避坑指南

I3C 比 I2C 快 10 倍?这句话在嵌入式群里传了很久,每次都能吵出一堆截图。前段时间我正好在 RK3576 上调板级 I3C 接口,从控制器寄存器一路摸到 Linux DTS 配置,踩了不少坑,也把这笔速度账彻底算明白了。本文就用 RK35…

2026/9/30 0:01:22

字符串转对象:JSON.parse、new Function与URLSearchParams

“字符串转对象”这几个字,我在技术群里见过的问法至少有十几种:有人拿着一串{a:1,b:2}说 JSON.parse 直接报错,有人要从 URL 里抠出参数,还有人只是想把abc变成能挂属性的东西。js 这门语言里,字符串和对象之间的转换…

2026/9/29 3:53:39

USB Type-C PCB布局分区设计:电源、高速信号与PD协议全攻略

做硬件这行,Type-C接口算是典型的“看着简单,做起来全坑”的东西。光引脚就24个,高低速信号、电源、控制线全部塞在一个小小的连接器里,如果PCB布局不做规划,打样回来基本就是“插上没反应”、“高速掉线”、“静电一打…

2026/9/29 9:46:12

系统编程学习原型如何补齐稳定性边界

系统编程学习原型如何补齐稳定性边界预算有限时&#xff0c;我先优化明显多余的复制&#xff0c;而不是猜测性地换容器。用借用传递只读数据通常就能减少分配&#xff1a; fn parse(line: &str) -> Result<Item, Error> { /* ... */ }用基准确认热点确实在分配&am…

2026/9/29 6:36:14

雨花区哪家财务公司代理记账比较好?

在雨花区&#xff0c;企业处理财税事务常常面临诸多挑战&#xff0c;选择一家靠谱的财务公司至关重要。湖南巨勤财务管理咨询有限公司就是本地正规实体财税服务机构&#xff0c;深耕本地工商财税行业多年&#xff0c;熟悉当地工商局、税务局最新政策与申报流程。主营公司注册、…

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑