当前位置: 首页 > news >正文

【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

题目链接&#xff1a; https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/ 1. 题目介绍&#xff08;04. 二维数组中的查找&#xff09; 在一个 n * m 的二维数组中&#xff0c;每一行都按照从左到右 非递减 的顺序排序&#xff0c;每一列都按照从上到下 非递…...

TDengine 3.0.2.5 查询再优化!揭秘索引文件的工作原理

TDengine 3.0 虽然对底层做了大规模的优化重构&#xff0c;但是相对于数据文件的工作逻辑和 2.0 相比是整体保持不变的。本系列文章的主旨在于帮助用户深入理解产品&#xff0c;并且拥有基本的性能调试思路&#xff0c;从而获得更好的产品体验。本期文章会在讲解 TDengine 时序…...

蓝牙耳机哪个品牌性价比高?性价比高的无线蓝牙耳机

现如今耳机已经十分普及&#xff0c;大多数人会随身佩戴蓝牙耳机&#xff0c;相较于传统耳机&#xff0c;无线耳机不仅携带方便&#xff0c;舒适度上也更加出色。不过市面上的无线耳机种类繁多&#xff0c;很多朋友不知道该如何挑选&#xff0c;所以小编特意整理了一期性价比高…...

python的disutils创建分发包

python中的distutils包主要用创建共享包&#xff0c;安装包&#xff0c;在平时安装python模块的时候&#xff0c;使用的命令如下&#xff1a; python setup.py install 其实以上代码就是distuitls包提供的功能&#xff0c;直接使用setup.py来进行安装一个包&#xff0c;在用这种…...

【洛谷】P1195 口袋的天空

明显看出为最小生成树&#xff0c;那么&#xff1a;难点在哪里呢&#xff1f;if(cntn-k)//******{flag1;break;}为什么是cntn-k呢而不是k呢&#xff1f;&#xff01;&#xff01;&#xff01;解释&#xff1a;&#xff08;如果每个已经连在一起了就不能分开&#xff0c;不管多少…...

JavaScript高级程序设计读书分享之3章——3.5操作符

JavaScript高级程序设计(第4版)读书分享笔记记录 适用于刚入门前端的同志 目录 操作符 一元操作符 递增/递减操作符 一元加和减 布尔操作符 逻辑非 逻辑与 逻辑或 乘性操作符 乘法操作符 除法操作符 取模操作符 加性操作符 加法操作符 减法操作符 关系操作符 相等操…...

moveToCoordinateF3DconcatenateRotations

moveToCoordinate 演示视频: 注意:前提是3~6轴机器人机构且不是PickAndPlace 该方法_3D。Poses.moveToCoordinate 移动由 指定的对象,该对象 对应于支持的机器人配置之一,只要标识的机器人配置支持,其第一个动画指向指定坐标和指定旋转。这无需您定义姿势即可工作。 工…...

多线程面试题开胃菜6(5道)

一、Fork/Join 框架是干什么的&#xff1f;大任务自动分散小任务&#xff0c;并发执行&#xff0c;合并小任务结果。二、线程数过多会造成什么异常&#xff1f;线程过多会造成栈溢出&#xff0c;也有可能会造成堆异常。三、说说线程安全的和不安全的集合。Java 中平时用的最多的…...

植物大战 List——C++

这里写目录标题vector和stirng的细节对于stringlist的使用list的迭代器反向迭代器构造函数关于list::sort的排序uniquelist的底层模拟实现结点类的实现迭代器模拟实现list实现插入的实现迭代器失效inserterase析构函数拷贝构造赋值构造函数vector和stirng的细节 复习vector的深…...

安灯(andon)系统是车间现场管理的必备工具

安灯&#xff08;andon&#xff09;系统应用越来越广泛&#xff0c;不单单局限于汽车行业&#xff0c;更多生产型企业意识到了提高工作效率的重要性&#xff0c;提高工作效率根本的能提高生产水平&#xff0c;提高产量&#xff0c;而且安灯&#xff08;andon&#xff09;系统不…...

Hazel游戏引擎(004)

本人菜鸟&#xff0c;文中若有代码、术语等错误&#xff0c;欢迎指正 我写的项目地址&#xff1a;https://github.com/liujianjie/GameEngineLightWeight&#xff08;中文的注释适合中国人的你&#xff09; 文章目录前言操作步骤讲解GitHubHazel项目此项目定位项目属性修改Sand…...

【CS224W】(task4)图嵌入表示学习

note node2vec&#xff1a; 计算随机游走概率从节点uuu开始模拟rrr条长度为lll的游走链路使用 Stochastic Gradient Descent 优化损失函数 Node2vec在节点分类方面表现更好&#xff1b;而其他方法在链路预测上效果更好&#xff0c;如random walk效率更高&#xff1b;graph emb…...

分享111个HTML医疗保健模板,总有一款适合您

分享111个HTML医疗保健模板&#xff0c;总有一款适合您 111个HTML医疗保健模板下载链接&#xff1a;https://pan.baidu.com/s/1YInaQDnUVsXYtMh1Ls-BHg?pwdxvfc 提取码&#xff1a;xvfc Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 import os import shuti…...

山东大学2022操作系统期末

接力&#xff1a;山东大学2021操作系统期末 2022—2023山东大学计算机操作系统期末考试回忆版 简答题(4 10 points) &#xff08;1&#xff09;用户态&#xff0c;核心态是什么 &#xff08;2&#xff09;这种区分对现代操作系统的意义 &#xff08;3&#xff09;printf(“…...

Hadoop高可用搭建(一)

目录 创建多台虚拟机 修改计算机名称 快速生效 修改网络信息 重启网络服务 关闭和禁用每台机的防火墙 同步时间 安装ntpdate 定时更新时间 启动定时任务 设置集群中每台机器的/etc/hosts 把hosts拷贝发送到每一台虚拟机 配置免密登陆 将本机的公钥拷贝到要免密登…...

算法 - 剑指Offer 重建二叉树

题目 输入某二叉树的前序遍历和中序遍历的结果&#xff0c;请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 解题思路 这题较为复杂&#xff0c; 首先审题&#xff0c;前序遍历规则&#xff1a;根左右&#xff0c; 中序遍历&#x…...

手写JavaScript常见5种设计模式

想分享的几种设计模式 目前模式&#xff1a;工厂模式&#xff0c;单例模式&#xff0c;适配器模式&#xff0c;装饰者模式&#xff0c;建造者模式 建造者模式 简介&#xff1a;建造者模式&#xff08;builder pattern&#xff09;比较简单&#xff0c;它属于创建型模式的一种…...

Python 异步: 当前和正在运行的任务(9)

我们可以反省在 asyncio 事件循环中运行的任务。这可以通过为当前运行的任务和所有正在运行的任务获取一个 asyncio.Task 对象来实现。 1. 如何获取当前任务 我们可以通过 asyncio.current_task() 函数获取当前任务。此函数将为当前正在运行的任务返回一个任务对象。 ... # …...

REDIS-雪崩、击穿、穿透

直接发车&#x1f697; 一.雪崩 1.触发原因 A.大量缓存数据在同一时间过期(失效) B.redis故障宕机 上述均导致全部请求去访问数据库&#xff0c;导致DB压力骤增&#xff0c;严重则导致数据库宕机/系统宕机 2.应对策略 不同触发原因&#xff0c;应对策略也不一致 应对A&a…...

什么人合适学习Python

发了几天的Python基础&#xff0c;也认识了一些朋友&#xff0c;忽然有人问起&#xff0c;说为啥学Python&#xff0c;或者说啥人学习Python&#xff0c;作为一个教龄8年从Python一线讲师到Python教学主管的我和大家分享一下个人的看法&#xff0c;还是提前说一下&#xff0c;个…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...