深入解析二维矩阵搜索:LeetCode 74与240题的两种高效解法对比
文章目录
- @[toc]
- **引言**
- **一、问题背景与排序规则对比**
- **1. LeetCode 74. 搜索二维矩阵**
- **2. LeetCode 240. 搜索二维矩阵 II**
- **二、核心解法对比**
- **方法1:二分查找法(适用于LeetCode 74)**
- **方法2:线性缩小搜索范围法(适用于LeetCode 240)**
- **三、关键差异与适用场景**
- **四、为什么解法不能互换?**
- **1. 二分查找法在LeetCode 240中的失效示例**
- **2. 线性缩小法在LeetCode 74中的效率问题**
- **五、边界情况处理**
- **1. 空矩阵或空行**
- **2. 单元素矩阵**
- **3. 单行或单列矩阵**
- **六、总结与建议**
文章目录
- @[toc]
- **引言**
- **一、问题背景与排序规则对比**
- **1. LeetCode 74. 搜索二维矩阵**
- **2. LeetCode 240. 搜索二维矩阵 II**
- **二、核心解法对比**
- **方法1:二分查找法(适用于LeetCode 74)**
- **方法2:线性缩小搜索范围法(适用于LeetCode 240)**
- **三、关键差异与适用场景**
- **四、为什么解法不能互换?**
- **1. 二分查找法在LeetCode 240中的失效示例**
- **2. 线性缩小法在LeetCode 74中的效率问题**
- **五、边界情况处理**
- **1. 空矩阵或空行**
- **2. 单元素矩阵**
- **3. 单行或单列矩阵**
- **六、总结与建议**
引言
在算法面试中,二维矩阵搜索问题频繁出现,其中 LeetCode 74. 搜索二维矩阵 和 LeetCode 240. 搜索二维矩阵 II 是两道经典的题目。尽管题目名称相似,但它们的矩阵排序规则和解题思路存在显著差异。本文将从问题本质出发,对比两种解法的核心思想、适用场景及实现细节,帮助读者深入理解并灵活应对类似问题。
一、问题背景与排序规则对比
1. LeetCode 74. 搜索二维矩阵
- 题目描述
在一个m x n
的二维矩阵中,每一行元素严格递增,且下一行的第一个元素严格大于上一行的最后一个元素。要求判断目标值target
是否存在于矩阵中。 - 排序特性
整个矩阵可以视为一个全局有序的一维数组,例如:
展开后为一维数组:[[1, 3, 5, 7],[10,11,16,20],[23,30,34,60]]
[1,3,5,7,10,11,16,20,23,30,34,60]
。
2. LeetCode 240. 搜索二维矩阵 II
- 题目描述
在一个m x n
的二维矩阵中,每一行元素从左到右递增,每一列元素从上到下递增,但行与行之间没有严格的大小关系。要求判断目标值是否存在。 - 排序特性
矩阵仅局部有序,无法直接展开为全局有序的一维数组,例如:[[1, 4, 7],[2, 5, 8],[3, 6, 9]]
二、核心解法对比
方法1:二分查找法(适用于LeetCode 74)
-
核心思想
将二维矩阵映射为一维数组,利用二分查找直接定位目标值。 -
时间复杂度
(O(\log(m \times n))),其中 (m) 为行数,(n) 为列数。 -
实现步骤
- 将二维索引映射为一维:
index = row * n + col
。 - 通过一维索引的二分查找确定目标值的位置。
- 转换回二维索引进行值比较。
- 将二维索引映射为一维:
-
Java代码实现
class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;int m = matrix.length, n = matrix[0].length;int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;int row = mid / n; // 计算行坐标int col = mid % n; // 计算列坐标if (matrix[row][col] == target) {return true;} else if (matrix[row][col] < target) {left = mid + 1;} else {right = mid - 1;}}return false;} }
方法2:线性缩小搜索范围法(适用于LeetCode 240)
-
核心思想
从矩阵的右上角(或左下角)出发,通过逐步排除行或列缩小搜索范围。 -
时间复杂度
(O(m + n)),其中 (m) 为行数,(n) 为列数。 -
实现步骤
- 初始化位置为右上角
(0, n-1)
。 - 若当前值等于目标值,返回
true
。 - 若当前值大于目标值,向左移动一列;否则向下移动一行。
- 重复直至越界。
- 初始化位置为右上角
-
Java代码实现
class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;int m = matrix.length, n = matrix[0].length;int row = 0, col = n - 1; // 从右上角开始搜索while (row < m && col >= 0) {int current = matrix[row][col];if (current == target) {return true;} else if (current > target) {col--; // 排除当前列} else {row++; // 排除当前行}}return false;} }
三、关键差异与适用场景
对比维度 | 二分查找法(LeetCode 74) | 线性缩小法(LeetCode 240) |
---|---|---|
时间复杂度 | (O(\log(mn)))(对数级,高效) | (O(m + n))(线性级,适用于中等规模矩阵) |
空间复杂度 | (O(1))(原地操作) | (O(1))(原地操作) |
排序规则依赖 | 必须全局有序 | 仅需局部行列有序 |
适用题目 | 仅LeetCode 74 | 仅LeetCode 240(但LeetCode 74也可用) |
优势场景 | 大规模全局有序矩阵 | 局部有序或中等规模矩阵 |
四、为什么解法不能互换?
1. 二分查找法在LeetCode 240中的失效示例
- 矩阵示例
[[1, 3, 5],[2, 4, 6],[7, 8, 9] ]
- 搜索目标:
2
- 一维展开为
[1,3,5,2,4,6,7,8,9]
,二分查找时中间值可能跳过实际存在的元素,导致错误结果。
- 一维展开为
2. 线性缩小法在LeetCode 74中的效率问题
- 矩阵示例
[[1, 3, 5, 7],[10,11,16,20],[23,30,34,60] ]
- 搜索目标:
60
- 从右上角开始需遍历
7 → 20 → 60
,时间复杂度为 (O(n)),而二分查找仅需 (O(\log 12) \approx 4) 次比较。
- 从右上角开始需遍历
五、边界情况处理
1. 空矩阵或空行
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
2. 单元素矩阵
- 矩阵为
[[5]]
,目标值为5
时直接返回true
。
3. 单行或单列矩阵
- 单行矩阵
[[1,3,5]]
或单列矩阵[[2],[4],[7]]
,两种方法均能正确处理。
六、总结与建议
-
LeetCode 74(全局有序)
- 优先选择二分查找法,时间复杂度更低,适合大规模数据。
- 若使用线性缩小法,虽然可行,但效率略低。
-
LeetCode 240(局部有序)
- 必须使用线性缩小法,二分查找法因全局无序可能失效。
- 从右上角或左下角出发均可,逻辑对称。
-
实际应用场景
- 数据库索引查询(全局有序场景)。
- 图像处理中的局部特征搜索(局部有序场景)。
通过深入理解矩阵的排序规则与算法特性,读者可以灵活选择最优解法,轻松应对二维矩阵搜索问题。无论是面试还是实际工程应用,清晰的思路和高效的代码实现都是解决问题的关键。
相关文章:
深入解析二维矩阵搜索:LeetCode 74与240题的两种高效解法对比
文章目录 [toc]**引言** **一、问题背景与排序规则对比****1. LeetCode 74. 搜索二维矩阵****2. LeetCode 240. 搜索二维矩阵 II** **二、核心解法对比****方法1:二分查找法(适用于LeetCode 74)****方法2:线性缩小搜索范围法&…...
Qt案例 以单线程或者单生产者多消费者设计模式实现QFTP模块上传文件夹功能
前文:Qt案例 使用QFtpServerLib开源库实现Qt软件搭建FTP服务器,使用QFTP模块访问FTP服务器 已经介绍了Qt环境下搭建FTP服务器或者使用QFTP上传的方式示例, 这里主要介绍下使用QFTP模块上传整个文件夹的案例示例。 目录导读 前因后果单线程处理1.定义FTPFolderUpload 继承 QT…...
含锡废水回收率提升技术方案
一、预处理环节优化 物理分离强化 采用双层格栅系统(孔径1mm0.5mm)拦截悬浮物,配套旋流分离器去除密度>2.6g/cm的金属颗粒,使悬浮物去除率提升至85%。增设pH值智能调节模块,通过在线pH计联动碳酸钠/氢氧化钠投加系…...
第八章,STP(生成树协议)
广播风暴----广播帧在二层环路中形成逆时针或顺时针的转动的环路,并且无限循环,最终导致设备宕机,网络瘫痪。 MAC地址表的翻摆(漂移)----同一个数据帧,顺时针接收后将记录MAC地址及接口的对应信息ÿ…...
《面向对象程序设计-C++》实验五 虚函数的使用及抽象类
程序片段编程题 1.【问题描述】 基类shape类是一个表示形状的抽象类,area( )为求图形面积的函数。请从shape类派生三角形类(triangle)、圆类(circles)、并给出具体的求面积函数。注:圆周率取3.14 #include<iostream> #in…...
PCIe - ZCU106(RC) + KU5P(EP) + 固化
目录 1. 简介 1.1 Data Mover 1.2 描述符 2. ZCU102 2.1 Ubuntu OS 2.2 USB Host 2.2.1 连接拓扑 2.2.2 设备类型 2.2.3 USB 跳帽设置 2.3 无线网卡 2.4 PCIe Info 2.4.1 Diagram 2.4.2 lspci -tv 2.4.3 lspci -v 2.4.2.1 设备基本信息 2.4.2.2 控制与状态寄存…...
网络编程核心技术解析:从Socket基础到实战开发
网络编程核心技术解析:从Socket基础到实战开发 一、Socket编程核心基础 1. 主机字节序与网络字节序:数据传输的统一语言 在计算机系统中,不同架构对多字节数据的存储顺序存在差异,而网络通信需要统一的字节序标准,这…...
SQL注入总结
一.sql注入 原理:当一个网站存在与用户交互的功能(如登录表单、搜索框、评论区等),并且用户输入的数据未经充分过滤或转义,直接拼接到后台数据库查询语句中执行时,就可能引发SQL注入漏洞。攻击者可以通过构…...
conda 安装cudnn
通过 Conda 安装 cuDNN 确保你有 NVIDIA GPU 和 CUDA Toolkit:首先,确保你的系统上安装了 NVIDIA GPU 和 CUDA Toolkit。你可以通过运行以下命令来检查 CUDA 是否已安装:nvcc --version 如果没有安装 CUDA,你需要先从 NVIDIA CU…...
强啊!Oracle Database 23aiOracle Database 23ai:使用列别名进行分组排序!
大家好,这里是架构资源栈!点击上方关注,添加“星标”,一起学习大厂前沿架构! 从 Oracle Database 23ai 开始,您可以在 GROUP BY 和 HAVING 子句中直接使用列别名。此功能在早期版本的 Oracle Database 中不…...
RAG 2.0 深入解读
一、Introduction 过去一年可谓是RAG元年,检索增强生成技术迅速发展与深刻变革,其创新与应用已深刻重塑了大模型落地的技术范式。站在2025年,RAG不仅突破了早期文本处理的局限,更通过多模态融合、混合检索优化和语义鸿沟跨越等突…...
Excel Vlookup
VLOOKUP(A2, Sheet2!A:B, 2, 0) 代表的是检查A2,匹配源是sheet2表AB两列 Sheet2!A:B:指定要在其中查找数据的范围,这里是 Sheet12中的 A 列和 B 列,A 列是查找的依据列,B 列是要返回值的列。2:表示要返回查找区域中的…...
css媒体查询及css变量
媒体查询是 CSS 样式表最重要的功能之一,所谓媒体查询指的就是根据不同的媒体类型(设备类型)和条件来区分各种设备(例如:电脑、手机、平板电脑、盲文设备等),并为它们分别定义不同的 CSS 样式。…...
CSS网格布局
网格布局将元素占用的空间划分为二维格子,下级元素放置在格子所在的位置上。划分格子的元素叫做网格容器,其 display 属性是 grid (块元素)或 inline-grid (内联块元素)。网格容器的下级元素叫做网格项。容…...
Windows远程连接MySQL报错,本地navicat能连接MySQL
一、报错 telnet 119.87.111.79 3306“无法打开到主机的连接。在端口 3306: 连接失败” 表明无法通过 TCP 协议连接到目标服务器的 3306 端口。 二、目的 (1)Telnet 测试的目的 Telnet 仅用于测试 TCP 端口是否开放ÿ…...
Github打不开怎么办?
国内无法打开github,使有watt toolkit一键加速即可打开。 加速器 加速器直接加速Github原站,在开发者使用或者需要登录账号时非常有效 Watt Toolkit(原Steam) 官网地址:Watt Toolkit 一、进入官网后,点…...
亿级流量系统架构设计与实战(四)
本章关键词 : 读 / 写分离 、 数据缓存 、 缓存更新 、 CQRS 、 数据分片 、 异步写。 高并发架构设计的要点 形成高并发系统的必要条件 高性能、高可用、可扩展。 高性能: 性能代表一个系统的并行处理能力,在同样的硬件设备条件下 , 性能越高 , 越能节约硬件资源。高可…...
Java基础问题——八股盛宴 | 3w字分享
目录 面向对象与面向过程的区别? Java面向对象有哪些特征,如何应用? 介绍下Java中的四种引用? Java中创建对象有几种方式? Java中的序列化和反序列化是什么? 什么是Java中不可变类? Java…...
保障企业的数据安全需要做什么?
守护企业数据安全,犹如构筑一座固若金汤的城堡,需要从技术壁垒、管理护城河、流程吊桥和人员守卫等多维度精心布局,打造环环相扣的立体防御体系。我们从以下关键项分析: 一、技术层面 数据加密 对敏感数据(如客户信息、…...
Flutter开发IOS蓝牙APP的大坑
Core Bluetooth 框架限制:iOS 的 Core Bluetooth 框架存在限制,如果指定的特征配置同时允许通知(Notifications)和指示(Indications),调用相关方法设置通知值时,默认仅会开启通知功能…...
LeetCode 解题思路 45(分割等和子集、最长有效括号)
解题思路: dp 数组的含义: 在数组中是否存在一个子集,其和为 i。递推公式: dp[i] | dp[i - num]。dp 数组初始化: dp[0] true。遍历顺序: 从大到小去遍历,从 i target 开始,直到 …...
AI Agent 入门指南:从 LLM 到智能体
AI. AI. AI. 最近耳朵里是不是总是被这些词轰炸?特别是“Agent”、“AI Agent”、“智能体”、“Agentic”…… 感觉一夜之间,AI 就从我们熟悉的聊天框里蹦出来,要拥有“独立思考”和“自主行动”的能力了? 说实话,一…...
高级java每日一道面试题-2025年5月02日-基础篇[反射篇-编码]-使用反射,获取Class对象
如果有遗漏,评论区告诉我进行补充 面试官: 编写代码通过三种方式(类名.class、对象.getClass()、Class.forName())获取java.util.ArrayList的Class对象。 我回答: 在Java中,反射(Reflection)是一种强大的机制&#…...
【bug】fused_bias_act_kernel.cu卡住没反应
简述 在推理人脸修复face restoration算法 GPEN的时候,发现有时候fused_bias_act_kernel.cu卡住没反应。 解决 清理下缓存,让程序自己再编译下...
小游戏(2)扫雷游戏
一、简述 鸽子的时间太长了,其实学完数组和函数就应该搞出来这个丐版的小游戏了,不耽误,反正总归是轮到了,嘻嘻。 二、依旧菜单\. 我们这里写的是一个丐版的扫雷游戏,难度就固定了,所以菜单写起来就是玩游…...
如何在vscode中set the environment variable `TF_ENABLE_ONEDNN_OPTS=0`
1.打开工作区设置文件 在 VS Code 中通过文件 -> 首选项 -> 设置,接着在设置窗口的右上角点击打开设置(JSON),这会打开settings.json文件。 2.添加环境变量设置 "terminal.integrated.env.linux": { "TF_EN…...
leetcode 24. 两两交换链表中的节点
题目描述 代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next…...
微调大模型如何准备数据集——常用数据集,Alpaca和ShareGPT
微调大模型如何准备数据集——常用数据集,Alpaca和ShareGPT 数据集准备常用数据集自定义数据集AlpacaShareGPT数据集准备 常用数据集 预训练数据集 Wiki Demo (en)RefinedWeb (en)RedPajama V2 (en)Wikipedia (en)Wikipedia (zh)Pile (en)...
使用Homebrew下载配置git和连接GitHub(Mac版)
本文详细介绍了在M系列Mac上安装Homebrew并配置Git的过程,包括git的下载、设置全局用户名和邮箱、生成SSH密钥、添加GitHubSSH密钥以及终端验证。这些步骤有助于用户顺利进行协同开发。 一、下载git 1、终端输入一下命令 brew install git2、这时下载完成 二、配…...
电子电器架构 --- 网关转发时延解析
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 钝感力的“钝”,不是木讷、迟钝,而是直面困境的韧劲和耐力,是面对外界噪音的通透淡然。 生活中有两种人,一种人格外在意别人的眼光;另一种人无论…...
shell-流程控制-循环-函数
1. 2. 3.获取当前目录下的普通文件的文件名作为变量列表打印输出 4.打印出下面语句中字符数不大于6的单词 rabbit is favorite to eat cabbage 5.Shell允许用户指定for语句的步长。当用户需要另外指定步长时 6.批量创建用户: 用户名以test开头,按数字序号…...
Paramiko 性能优化详解
1. 复用连接:减少 SSH 连接开销 SSH 连接的建立涉及 TCP 握手、密钥交换、身份认证等步骤,频繁创建连接会显著降低性能。复用连接是核心优化手段。 优化方法 手动创建 Transport 对象并复用通过同一 Transport 执行多种操作(命令、SFTP、端…...
代码随想录图论part03
第十一章:图论part03 孤岛的总面积 (深搜) 代码随想录 孤岛问题:先处理边缘岛在处理孤岛 沉没孤岛 (广搜) 代码随想录 水流问题 代码随想录 目的:找水源 思路;逆向思考,找两…...
树上背包学习笔记
树上背包,顾名思义,就是在树上跑背包。每日顾名思义 Q:那么到底为什么要树上跑背包 dp 呢? A:因为我们到现在学的背包 dp 还是属于较浅的一类,什么 01 背包、完全背包还是多重背包,但是如果这…...
CPU:为什么Ryzen 7000系列处理器PCIe通道总数是28,而可用的通道数是24?
AMD Ryzen 7000系列(Zen 4架构)处理器的 28条PCIe 5.0通道 中,有 4条固定用于连接主板芯片组(如X670/B650),剩余的 24条直接分配给用户设备。以下是具体分配逻辑: 1. PCIe通道的总分配 24条直连…...
OpenCV 图形API(80)图像与通道拼接函数-----仿射变换函数warpAffine()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 对图像应用仿射变换。 函数 warpAffine 使用指定的矩阵对源图像进行变换: dst ( x , y ) src ( M 11 x M 12 y M 13 , M 21 x M…...
巧记英语四级单词 Unit7-下【晓艳老师版】
navigate v. 航行,航空 那六扇门gatevibrate v.颤抖,抖动 男生早上起来看到六个文胸在那挂着,春心荡漾virtual a.事实上,实际上的 发音“龌龊”;通常lyvia prep.经过 a想成小乌龟,兔子想到河对面吃草&am…...
idea使用lombok错误,找不到符号,明明编译没问题,运行报错
lombok使用出现的问题 问题找不到方法 经常遇到这样的小伙伴看到这个是不是一头雾水,明明我编译没有我问题,运行就出现问题,真的很生气。 下面介绍解决这个问题的几种方法。 开启 annotation processing 开启之后重启,试试有…...
Transformer面经
请问你对Transformer有什么了解 简要回答的话可以这样: Transformer是一种基于自注意力机制的神经网络架构,它主要用于处理序列数据,如自然语言处理。 核心的组件有:自注意力机制(计算序列中每个元素与其他元素的相…...
学习Python的第二天之网络爬虫
30岁程序员学习Python的第二天之网络爬虫的信息提取 BeautifulSoup库 地址:https://beautifulsoup.readthedocs.io/zh-cn/v4.4.0/ 1、BeautifulSoup4安装 在windows系统下通过管理员权限运行cmd窗口 运行pip install beautifulsoup4 测试实例 import requests…...
【基础】Python包管理工具uv使用教程
一、uv简介 uv 是由 Astral(前身为 Basis)团队开发的 Python 包安装器和解析器,完全使用 Rust 语言编写。与传统 Python 工具不同,uv 将多个工具的功能整合到一个高性能的解决方案中,旨在提供更现代、更高效的 Python…...
【十五】Mybatis动态SQL实现原理
Mybatis动态SQL实现原理 目录 Mybatis动态SQL实现原理 概述 动态 SQL 实现原理 总结 概述 每天日常开发都在使用mybatis,但是很多人并没有花心思去理解mybatis的实现原理,一直处于使用阶段,程序员的使命是改变世界,这一点可能…...
UE5 把翅膀动画额外创建动画蓝图并和角色绑定混合动画
把翅膀和角色合并,把翅膀绑在Spine_3上 在5.3内,需要LayerSetup指定骨骼才能使用混合...
Coding Practice,48天强训(30)
Topic 1:爱吃素(素数性质) 爱吃素 在强训25的第一题我总结过关于素数的几种判断方式,如果忘了可以回去看 第一次写我是这样写的 #include <bits/stdc.h> using namespace std;bool isPrime(long long &a, long long …...
华为私有协议Hybrid
实验top图 理论环节 1. 基本概念 Hybrid接口: 支持同时处理多个VLAN流量,且能针对不同VLAN配置是否携带标签(Tagged/Untagged)。 核心特性: 灵活控制数据帧的标签处理方式,适用于复杂网络场景。 2. 工作…...
神经网络之互动练习详解:从基础到拟合非线性数据
神经网络之互动练习详解:从基础到拟合非线性数据 在机器学习的世界里,神经网络是一种强大而神奇的工具,它可以帮助我们解决各种复杂的问题。今天,我们就通过一个有趣的互动练习,来深入了解神经网络的工作原理以及如何…...
遨游科普:2025年,三防平板有多智能?
在极端环境与复杂场景中,专业设备的可靠性始终是行业应用的核心命题。随着物联网、5G通信与边缘计算技术的深度融合,三防平板已突破传统“坚固耐用”的单一属性,进化为集多模通讯、智能感知与场景化扩展于一体的移动智能终端。 AORO P9000三防…...
基于C++的IOT网关和平台7:github项目ctGateway设备协议开发指南
初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github:codetoys,所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C++的,可以在任何平台上使用。 源码指引:github源码指引_初级代码游戏的博客-CSDN博客 系…...
yolov8中的python基础--模块导入篇
import语句有几种不同的写法,它们有不同的用途和优势。 1. 直接 import 语法 import module_name 用途 导入整个模块,使用时需要通过模块名访问其中的内容。 示例 import os print(os.listdir()) # 必须用 os. 前缀 适用场景 当需要频繁使用模块…...
26.2Linux中SPI的驱动实验(编程)_csdn
我尽量讲的更详细,为了关注我的粉丝!!! 这里我们用到的是stm32mp157的板子,所以我们看一下SPI用到的引脚。 1、硬件原理图分析 SPI1_MOSI(对应芯片引脚 SDA/SDI ):主机输出从机输入…...