【LeetCode】剑指 Offer 04. 二维数组中的查找 p44 -- Java Version
题目链接: https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
1. 题目介绍(04. 二维数组中的查找)
在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
【测试用例】:
示例:
现有矩阵 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。
给定 target = 20,返回 false。
【条件约束】:
0 <= n <= 1000
0 <= m <= 1000
2. 题解
2.1 暴力枚举 – O(nm)
时间复杂度O(nm),空间复杂度O(1)
class Solution {// 暴力枚举public boolean findNumberIn2DArray(int[][] matrix, int target) {// 1. 判断数组是否为空,如果是则返回falseif (matrix.length <= 0) return false;// 2. 定义变量,记录二维数组的行列int n = matrix.length;int m = matrix[0].length;// 3. 循环遍历每一个值,直到找到正确结果for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (matrix[i][j] == target) return true;}}// 4. 循环结束,数组中不存在targetreturn false;}
}

2.2 “标记数”数组剔除 – O(n+m)
时间复杂度O(n+m),空间复杂度O(1)
class Solution {// 标记数数组剔除public boolean findNumberIn2DArray(int[][] matrix, int target) {// 1. 判断数组是否为空,如果是则返回falseif (matrix.length <= 0) return false;// 2. 定义变量,记录二维数组的行列int row = 0, col = matrix[0].length-1;// while (col >= 0 && row < matrix.length){if (matrix[row][col] > target) col--;else if (matrix[row][col] < target) row++;else return true;}// 4. 循环结束,数组中不存在targetreturn false;}
}

3. 思考
没想到,用穷举在力扣的测试用例里面也这么快,感觉还是约束条件太小了。
4. 参考资料
[1] 面试题04. 二维数组中的查找(标志数,清晰图解)
相关文章:
【LeetCode】剑指 Offer 04. 二维数组中的查找 p44 -- Java Version
题目链接: https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/ 1. 题目介绍(04. 二维数组中的查找) 在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递…...
TDengine 3.0.2.5 查询再优化!揭秘索引文件的工作原理
TDengine 3.0 虽然对底层做了大规模的优化重构,但是相对于数据文件的工作逻辑和 2.0 相比是整体保持不变的。本系列文章的主旨在于帮助用户深入理解产品,并且拥有基本的性能调试思路,从而获得更好的产品体验。本期文章会在讲解 TDengine 时序…...
蓝牙耳机哪个品牌性价比高?性价比高的无线蓝牙耳机
现如今耳机已经十分普及,大多数人会随身佩戴蓝牙耳机,相较于传统耳机,无线耳机不仅携带方便,舒适度上也更加出色。不过市面上的无线耳机种类繁多,很多朋友不知道该如何挑选,所以小编特意整理了一期性价比高…...
python的disutils创建分发包
python中的distutils包主要用创建共享包,安装包,在平时安装python模块的时候,使用的命令如下: python setup.py install 其实以上代码就是distuitls包提供的功能,直接使用setup.py来进行安装一个包,在用这种…...
【洛谷】P1195 口袋的天空
明显看出为最小生成树,那么:难点在哪里呢?if(cntn-k)//******{flag1;break;}为什么是cntn-k呢而不是k呢?!!!解释:(如果每个已经连在一起了就不能分开,不管多少…...
JavaScript高级程序设计读书分享之3章——3.5操作符
JavaScript高级程序设计(第4版)读书分享笔记记录 适用于刚入门前端的同志 目录 操作符 一元操作符 递增/递减操作符 一元加和减 布尔操作符 逻辑非 逻辑与 逻辑或 乘性操作符 乘法操作符 除法操作符 取模操作符 加性操作符 加法操作符 减法操作符 关系操作符 相等操…...
moveToCoordinateF3DconcatenateRotations
moveToCoordinate 演示视频: 注意:前提是3~6轴机器人机构且不是PickAndPlace 该方法_3D。Poses.moveToCoordinate 移动由 指定的对象,该对象 对应于支持的机器人配置之一,只要标识的机器人配置支持,其第一个动画指向指定坐标和指定旋转。这无需您定义姿势即可工作。 工…...
多线程面试题开胃菜6(5道)
一、Fork/Join 框架是干什么的?大任务自动分散小任务,并发执行,合并小任务结果。二、线程数过多会造成什么异常?线程过多会造成栈溢出,也有可能会造成堆异常。三、说说线程安全的和不安全的集合。Java 中平时用的最多的…...
植物大战 List——C++
这里写目录标题vector和stirng的细节对于stringlist的使用list的迭代器反向迭代器构造函数关于list::sort的排序uniquelist的底层模拟实现结点类的实现迭代器模拟实现list实现插入的实现迭代器失效inserterase析构函数拷贝构造赋值构造函数vector和stirng的细节 复习vector的深…...
安灯(andon)系统是车间现场管理的必备工具
安灯(andon)系统应用越来越广泛,不单单局限于汽车行业,更多生产型企业意识到了提高工作效率的重要性,提高工作效率根本的能提高生产水平,提高产量,而且安灯(andon)系统不…...
Hazel游戏引擎(004)
本人菜鸟,文中若有代码、术语等错误,欢迎指正 我写的项目地址:https://github.com/liujianjie/GameEngineLightWeight(中文的注释适合中国人的你) 文章目录前言操作步骤讲解GitHubHazel项目此项目定位项目属性修改Sand…...
【CS224W】(task4)图嵌入表示学习
note node2vec: 计算随机游走概率从节点uuu开始模拟rrr条长度为lll的游走链路使用 Stochastic Gradient Descent 优化损失函数 Node2vec在节点分类方面表现更好;而其他方法在链路预测上效果更好,如random walk效率更高;graph emb…...
分享111个HTML医疗保健模板,总有一款适合您
分享111个HTML医疗保健模板,总有一款适合您 111个HTML医疗保健模板下载链接:https://pan.baidu.com/s/1YInaQDnUVsXYtMh1Ls-BHg?pwdxvfc 提取码:xvfc Python采集代码下载链接:采集代码.zip - 蓝奏云 import os import shuti…...
山东大学2022操作系统期末
接力:山东大学2021操作系统期末 2022—2023山东大学计算机操作系统期末考试回忆版 简答题(4 10 points) (1)用户态,核心态是什么 (2)这种区分对现代操作系统的意义 (3)printf(“…...
Hadoop高可用搭建(一)
目录 创建多台虚拟机 修改计算机名称 快速生效 修改网络信息 重启网络服务 关闭和禁用每台机的防火墙 同步时间 安装ntpdate 定时更新时间 启动定时任务 设置集群中每台机器的/etc/hosts 把hosts拷贝发送到每一台虚拟机 配置免密登陆 将本机的公钥拷贝到要免密登…...
算法 - 剑指Offer 重建二叉树
题目 输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 解题思路 这题较为复杂, 首先审题,前序遍历规则:根左右, 中序遍历&#x…...
手写JavaScript常见5种设计模式
想分享的几种设计模式 目前模式:工厂模式,单例模式,适配器模式,装饰者模式,建造者模式 建造者模式 简介:建造者模式(builder pattern)比较简单,它属于创建型模式的一种…...
Python 异步: 当前和正在运行的任务(9)
我们可以反省在 asyncio 事件循环中运行的任务。这可以通过为当前运行的任务和所有正在运行的任务获取一个 asyncio.Task 对象来实现。 1. 如何获取当前任务 我们可以通过 asyncio.current_task() 函数获取当前任务。此函数将为当前正在运行的任务返回一个任务对象。 ... # …...
REDIS-雪崩、击穿、穿透
直接发车🚗 一.雪崩 1.触发原因 A.大量缓存数据在同一时间过期(失效) B.redis故障宕机 上述均导致全部请求去访问数据库,导致DB压力骤增,严重则导致数据库宕机/系统宕机 2.应对策略 不同触发原因,应对策略也不一致 应对A&a…...
什么人合适学习Python
发了几天的Python基础,也认识了一些朋友,忽然有人问起,说为啥学Python,或者说啥人学习Python,作为一个教龄8年从Python一线讲师到Python教学主管的我和大家分享一下个人的看法,还是提前说一下,个…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
python读取SQLite表个并生成pdf文件
代码用于创建含50列的SQLite数据库并插入500行随机浮点数据,随后读取数据,通过ReportLab生成横向PDF表格,包含格式化(两位小数)及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...
