LeetCode[中等] 74.搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。


public class Solution {public bool SearchMatrix(int[][] matrix, int target) {int m = matrix.Length, n = matrix[0].Length;int low = 0, high = m * n - 1;while(low <= high){int mid = low + (high - low) / 2;int row = mid / n , column = mid % n;if(matrix[row][column] == target)return true;else if(matrix[row][column] > target)high = mid -1;elselow = mid + 1;}return false;}
}
思路:m 行 n 列的矩阵可以转换成长度为 mn 的升序数组。矩阵中的每个位置可以和升序数组中的下标转换:
-
当 0≤i<m 且 0≤j<n 时,矩阵的第 i 行第 j 列等价于升序数组的下标 i×n+j;
-
当 0≤index<mn 时,升序数组的下标 index 等价于矩阵的第 ⌊nindex⌋ 行第 index mod n 列。
为了判断矩阵中是否存在目标值,可以在矩阵转换成的升序数组中二分查找。
复杂度分析
代码
测试用例
测试结果
测试结果
全部题解
74. 搜索二维矩阵
Storm

关注
242
2022.06.11
发布于 上海
数组
二分查找
矩阵
C
6+
解法
思路和算法
由于给定的矩阵满足每行升序排序,且每行的第一个整数大于前一行的最后一个整数,因此如果将矩阵的每一行拼接到前一行的末尾,可以得到一个升序数组,m 行 n 列的矩阵可以转换成长度为 mn 的升序数组。矩阵中的每个位置可以和升序数组中的下标转换:
-
当 0≤i<m 且 0≤j<n 时,矩阵的第 i 行第 j 列等价于升序数组的下标 i×n+j;
-
当 0≤index<mn 时,升序数组的下标 index 等价于矩阵的第 ⌊nindex⌋ 行第 indexmodn 列。
为了判断矩阵中是否存在目标值,可以在矩阵转换成的升序数组中二分查找。
用 low 和 high 分别表示二分查找的下标范围的下界和上界,初始时 low=0,high=mn−1。每次查找时,取 mid 为 low 和 high 的平均数向下取整,计算下标 mid 对应的矩阵行下标和列下标,判断矩阵中的相应位置的数和目标值的大小关系,调整查找的下标范围。
-
如果矩阵中相应位置的数等于 target,则找到目标值,返回 true。
-
如果矩阵中相应位置的数大于 target,则如果目标值存在,其下标一定小于 mid,因此在下标范围 [low,mid−1] 中继续查找。
-
如果矩阵中相应位置的数小于 target,则如果目标值存在,其下标一定大于 mid,因此在下标范围 [mid+1,high] 中继续查找。
如果查找的过程中出现 low>high,则目标值不存在,返回 false。
代码
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = low + (high - low) / 2;int row = mid / n, column = mid % n;if (matrix[row][column] == target) {return true;} else if (matrix[row][column] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}
复杂度分析
-
时间复杂度:O(log(mn)),其中 m 和 n 分别是矩阵 matrix 的行数和列数。矩阵中的元素个数是 mn,二分查找的次数是 O(log(mn)),每次查找的时间是 O(1),时间复杂度是 O(log(mn))。
-
空间复杂度:O(1)。
相关文章:
LeetCode[中等] 74.搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。…...
overleaf如何下载论文的pdf
用overleaf写完英文论文后,要将论文保存为PDF格式 点击图片中的下载按钮 然后选择一个路径保存论文的PDF格式即可。...
Java 每日一刊(第13期):this super static
“优秀的代码不仅仅是给机器看的,更是给人看的。” 前言 这里是分享 Java 相关内容的专刊,每日一更。 本期将为大家带来以下内容: this 关键字super 关键字static 关键字 this 关键字 this 关键字是 Java 中最常见的关键字之一…...
关于一些Spring的配置的作用
文章目录 spring.profiles.activejmx.default-domainmain.allow-bean-definition-overridingmain.allow-circular-referencescloud.nacoscloud.nacos.configcloud.nacos.shared-configsmvc.pathmatch.matching-strategy spring:profiles:active: ${config.profile}# include…...
利用Python与Ansible实现高效网络配置管理
利用Python与Ansible实现高效网络配置管理 在当今复杂多变的网络环境中,自动化配置管理工具成为了IT运维团队不可或缺的工具。Python以其强大的编程能力和丰富的库支持,结合Ansible这一流行的自动化运维工具,能够极大地提升网络配置管理的效…...
JDBC技术在不同数据库系统中的兼容性及Java数据库交互技术概览
目录 1. JDBC技术在不同数据库系统中的兼容性 2. 除了JDBC,还有哪些技术可以实现Java与数据库的交互? 3. 结论 在Java应用程序中,数据库交互是一个核心功能。Java Database Connectivity (JDBC) 是实现这一功能的标准技术之一。然而&#…...
双击热备 Electron网页客户端
安装流程: 1.下载node.js安装包进行安装 2.点击Next; 3.勾选,点击Next; 4.选择安装目录 5.选择Online 模式 6.下一步执行安装 。 7.运行cmd,执行命令 path 和 node --version,查看配置路径和版本 8.Goland安装插件node.js 9.配置运行…...
数据中台系统产品原型RP原型Axure高保真交互原型 源文件分享
在数字化时代,数据已经成为企业最宝贵的资产之一。为了更好地管理和利用这些数据,这边为大家整理了一套数据中台Axure高保真原型。这套原型致力于为企业提供全方位的数据服务,助力企业实现数据驱动的创新发展。 下载及预览地址:h…...
论文阅读笔记:Sapiens: Foundation for Human Vision Models
Sapiens: Foundation for Human Vision Models 1 背景1.1 问题1.2 目标 2 方法3 创新点4 模块4.1 Humans-300M数据集4.2 预训练4.3 2D位姿估计4.4 身体部位分割4.5 深度估计4.6 表面法线估计 5 实验5.1 实现细节5.2 2D位姿估计5.3 身体部位分割5.4 深度估计5.5 表面法线估计5.6…...
【学术会议:中国厦门,为全球的计算机科学与管理科技研究者提供一个国际交流平台】第五届计算机科学与管理科技国际学术会议(ICCSMT 2024)
您的学术研究值得被更多人看到! 在这里,我为您提供精准的会议推荐,包括计算机科学、管理科技、信息系统、人工智能、供应链管理等领域的国际会议。高效的稿件录用流程和优质的检索服务将确保您的研究成果迅速传播。关注我,寻找与…...
RK3588/RK3588s运行yolov8达到27ms
前言 Hello,小伙伴们~~我最近做了一个比较有意思的东西,想起来也好久没有写博客了,就记录一下吧。希望和大家一起学习,一起进步! 我简单介绍一下我最近做的这个东西的经过哈~上个月在B站上看到了一个博主发了一条视频关…...
2024年华为杯中国研究生数学建模竞赛E题(高速公路应急车道紧急启用模型)思路
1. 统计四个观测点的交通流参数随时间的变化规律 思路: 从视频数据中提取流量、密度、速度等交通流参数。进行时间序列统计,分析其随时间的变化规律。通过数据可视化,帮助分析流量波动、车速变化等现象。主要步骤: 读取视频数据:利用提供的Python程序读取每个视频文件。提…...
np.random.seed设完又想用随机seed怎么办
Python 设完np random seed 之后又想不设这个seed让它random,怎么办? 在Python的NumPy库中,一旦你设置了随机种子(通过numpy.random.seed()函数),所有后续的随机操作都会基于这个种子生成可预测的结果。如…...
[数据结构]动态顺序表的实现与应用
文章目录 一、引言二、动态顺序表的基本概念三、动态顺序表的实现1、结构体定义2、初始化3、销毁4、扩容5、缩容5、打印6、增删查改 四、分析动态顺序表1、存储方式2、优点3、缺点 五、总结1、练习题2、源代码 一、引言 想象一下,你有一个箱子(静态顺序…...
Invalid Private Key, Not a valid string or uint8Array
报这种错误:一般在生成private key前面添加"0x"即可解决。我就是在私钥前面添加了"0x"解决了。 在学习web3时,使用助词生成的私钥,然后由私钥导出keystore就报错: ERROR Invalid Private Key, Not a valid …...
【Text2SQL】PET-SQL:在Spider基准测试中取得了SOTA
解读:PET-SQL: A Prompt-enhanced Two-stage Text-to-SQL Framework with Cross-consistency 这篇论文介绍了一个名为 PET-SQL 的文本到 SQL(Text-to-SQL)框架,旨在通过增强提示(prompt)和利用不同大型语言…...
python-3n+1数链/233
一:3n1数链题目描述 在计算机科学上,有很多类问题是无法解决的,我们称之为不可解决问题。然而,在很多情况下我们并不知道哪一类问题可以解决,哪一类问题不可解决。现在我们就有这样一个问题,问题如下&#…...
vue2基础系列教程之v-model及面试高频问题
v-model是表单组件里面的核心知识点,这个指令给我们写表单业务带来了很大的方便。 元素标签上的 v-model 指令用于双向绑定数据,它是一个语法糖,可以用于代替 v-bind:value 和 input 例如:<input v-model"message" placeholder…...
【高分系列卫星简介——高分一号(GF-1)】
高分一号卫星(GF-1) 高分一号(GF-1)是中国高分辨率对地观测系统(简称“高分专项”)的第一颗卫星,具有里程碑式的意义。以下是对高分一号卫星的详细介绍: 一、基本信息 发射时间&…...
Python基于TensorFlow实现时间序列循环神经网络回归模型(LSTM时间序列回归算法)项目实战
说明:这是一个机器学习实战项目(附带数据代码文档视频讲解),如需数据代码文档视频讲解可以直接到文章最后获取。 1.项目背景 随着信息技术的发展和传感器设备的广泛应用,时间序列数据的产生量急剧增加。无论是股市价格…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
