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

Hot100 - 搜索二维矩阵II

Hot100 - 搜索二维矩阵II

image-20241130000301509

最佳思路:

利用矩阵的特性,针对搜索操作可以从右上角或者左下角开始。通过判断当前位置的元素与目标值的关系,逐步缩小搜索范围,从而达到较高的效率。

  • 从右上角开始:假设矩阵是升序排列的(每行和每列都升序)。如果当前位置的元素等于目标值,返回 true;如果当前位置的元素小于目标值,向下移动(行索引加 1);如果当前位置的元素大于目标值,向左移动(列索引减 1)。通过这种方式,可以快速排除不可能的部分。

时间复杂度:

  • 时间复杂度为 O(m+n)O(m + n),其中 mm 是矩阵的行数,nn 是矩阵的列数。在最坏情况下,最多需要检查一行和一列的元素。

思路解析:

  1. 从右上角开始搜索:矩阵的每一行是升序排列的,每一列也是升序排列的。从右上角元素开始,如果当前元素等于目标值,返回 true;如果小于目标值,则说明当前元素及其所在的列不可能包含目标值,向下移动;如果大于目标值,则说明当前元素及其所在的行不可能包含目标值,向左移动。
  2. 逐步缩小搜索范围:通过不断调整行列索引,逐步缩小可能包含目标值的区域,直到找到目标值或确定目标值不存在。

代码实现:

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;  // 行数int n = matrix[0].length;  // 列数int i = 0;  // 从第一行开始int j = n - 1;  // 从最后一列开始while (i < m && j >= 0) {if (matrix[i][j] == target) {return true;  // 找到目标值} else if (matrix[i][j] < target) {i++;  // 向下移动} else {j--;  // 向左移动}}return false;  // 没有找到目标值}
}

思路总结:

  • 优化搜索:通过从矩阵的右上角开始搜索,可以利用矩阵的行列升序特点,有效缩小搜索范围。
  • 时间复杂度:在最坏情况下,我们最多会搜索 m+nm + n 次元素,比直接遍历整个矩阵的 O(m×n)O(m \times n) 要高效得多。
  • 空间复杂度:此方法使用了常数空间 O(1)O(1),不需要额外的空间来存储数据。

相关文章:

Hot100 - 搜索二维矩阵II

Hot100 - 搜索二维矩阵II 最佳思路&#xff1a; 利用矩阵的特性&#xff0c;针对搜索操作可以从右上角或者左下角开始。通过判断当前位置的元素与目标值的关系&#xff0c;逐步缩小搜索范围&#xff0c;从而达到较高的效率。 从右上角开始&#xff1a;假设矩阵是升序排列的&a…...

uart_pl011.c驱动API的zephyr测试

API概述 本次测试针对uart的uart_poll_in和uart_poll_outAPI进行测试&#xff0c; uart_poll_in static int pl011_poll_in(const struct device *dev, unsigned char *c)这是一个轮询方式的接收函数&#xff1a; 功能&#xff1a;检查 UART 是否有新数据到达&#xff0c;如…...

RPA:电商订单处理自动化

哈喽&#xff0c;大家好&#xff0c;我是若木&#xff0c;最近闲暇时间较多&#xff0c;于是便跟着教程做了一个及RPA&#xff0c;谈到这个&#xff0c;可能很多人并不是很了解&#xff0c;但是实际上&#xff0c;这玩意却遍布文末生活的边边角角。话不多说&#xff0c;我直接上…...

小程序 - 个人简历

为了让招聘人员快速地认识自己&#xff0c;可以做一个“个人简历”微信小程序&#xff0c; 展示自己的个人信息。 下面将对“个人简历”微信小程序进行详细讲解。 目录 个人简历 创建图片目录 页面开发 index.wxml index.wxss 功能实现截图 总结 个人简历 创建图片目录…...

MySQL自启动失败(MySQL不能开机自启)解决方案_MySQL开机自启疑难杂症解决,适用Win11/Win10

问题描述&#xff08;MySQL 开机自启失败&#xff09; 本文解决方法&#xff0c;在 windows10 、 windows11 系统中均可使用。 win11 安装 MySQL 后&#xff0c;不能开机自启。 在服务中&#xff0c;手动启动服务后&#xff0c;可正常使用&#xff0c;一点异常都没有。 或者…...

储存水..

问题描述: 给定m个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子下雨之后能储存多少水. 思路解析: 思考一下,什么样的位置能盛水?只有在当前柱子的左边和右边都比它高的情况下才能储存住水,而储水量和左侧最高柱及右侧最高柱有关.具体来说就是和左右两侧最矮的…...

Cmake 常用操作总结

CMakeLists.txt结构 总结该文件的主要结构 cmake_minimum_required(VERSION <version>) 指定CMake的最低版本&#xff0c;一般都是根据项目需要设定 cmake_minimum_required(VERSION 3.10) project(<name>) 定义项目的名称&#xff0c;放在CMake的开头 project(…...

Kylin Server V10 下 RocketMQ 主备自动切换模式部署

一、NameServer简介 NameServer 是一个注册中心,提供服务注册和服务发现的功能。NameServer 可以集群部署,集群中每个节点都是对等的关系,节点之间互不通信。 服务注册 Broker 启动的时候会向所有的 NameServer 节点进行注册,注意这里是向集群中所有的 NameServer 节点注册…...

DevOps工程技术价值流:GitLab源码管理与提交流水线实践

在当今快速迭代的软件开发环境中&#xff0c;DevOps&#xff08;开发运维一体化&#xff09;已经成为提升软件交付效率和质量的关键。而GitLab&#xff0c;作为一个全面的开源DevOps平台&#xff0c;不仅提供了强大的版本控制功能&#xff0c;还集成了持续集成/持续交付(CI/CD)…...

Vue 3 中实现页面特定功能控制

在开发 Vue 应用时&#xff0c;我们经常会遇到需要在特定页面启用或禁用某些功能的情况。本文将以 A父.vue 页面为例&#xff0c;探讨如何在点击汇总菜单时仅在该页面生效&#xff0c;而在其他页面不生效的问题。 1. 利用 Vue 3 的 provide 和 inject 实现状态传递 Vue 3 提供…...

VLC 播放的音视频数据处理流水线搭建

VLC 用 input_thread_t 对象直接或间接管理音视频播放有关的各种资源,包括 Access,Demux,Decode,Output,Filter 等,这个类型定义 (位于 vlc-3.0.16/include/vlc_input.h) 如下: struct input_thread_t {VLC_COMMON_MEMBERS };input_thread_t 是个抽象类型,VLC 中这个类…...

何时在 SQL 中使用 CHAR、VARCHAR 和 VARCHAR(MAX)

在管理数据库表时&#xff0c;考虑 CHAR、VARCHAR 和 VARCHAR(MAX) 是必不可少的。此外&#xff0c;使用正确的工具&#xff08;例如dbForge Studio for SQL Server&#xff09; &#xff0c;与数据库相关的任务都会变得更加容易。它是针对 SQL Server 专业人员的强大的一体化解…...

学习笔记043——HashMap源码学习1

文章目录 1、HashMap2、Hashtable3、TreeMap4、HashMap 底层结构4.1、什么是红黑树&#xff1f; 1、HashMap HashMap key 是不能重复的&#xff0c;value 可以重复 底层结构 key-value 进行存储&#xff0c;key-value 存入到 Set 中&#xff0c;再将 Set 装载到 HashMap pack…...

单点登录原理

允许跨域–>单点登录。 例如https://www.jd.com/ 同一个浏览器下&#xff1a;通过登录页面产生的cookie里的一个随机字符串的标识&#xff0c;在其他子域名下访问共享cookie获取标识进行单点登录&#xff0c;如果没有该标识则返回登录页进行登录。 在hosts文件下面做的域名…...

【随笔】AI大模型对软件开发的影响

随着 AI 技术的不断发展&#xff0c;AI大模型正在重塑软件开发流程&#xff0c;从代码自动生成到智能测试&#xff0c;未来&#xff0c;AI 大模型将会对软件开发者、企业&#xff0c;以及整个产业链都产生深远的影响。欢迎探讨 AI 是如何重塑软件开发的各个环节以及带来的新的流…...

JAVA中接口类和抽象类的区别

在Java中&#xff0c;接口&#xff08;Interface&#xff09;和抽象类&#xff08;Abstract Class&#xff09;都是实现抽象概念的方式&#xff0c;但它们之间存在一些关键的区别&#xff1a; 1. 定义和声明 抽象类&#xff1a; 使用abstract关键字声明。可以包含构造方法、成…...

【AI系统】昇腾 AI 架构介绍

昇腾 AI 架构介绍 昇腾计算的基础软硬件是产业的核⼼&#xff0c;也是 AI 计算能⼒的来源。华为&#xff0c;作为昇腾计算产业⽣态的⼀员&#xff0c;是基础软硬件系统的核⼼贡献者。昇腾计算软硬件包括硬件系统、基础软件和应⽤使能等。 而本书介绍的 AI 系统整体架构&#…...

uniapp input只输入一个字符就自动失去焦点

下面一段代码在每次输入后自动失去焦点&#xff0c;这是因为绑定的:key是动态的&#xff0c;输入改变后都需要重新刷新渲染&#xff0c;这是造成input只能输入一次就自动失去焦点的原因。 <view class"" v-for"(item, index) in phoneList" :key"…...

定时/延时任务-ScheduledThreadPoolExecutor的使用

文章目录 1. 概要2. 固定速率和固定延时2.1 固定速率2.2 固定延时 3. API 解释3.1 schedule3.2 固定延时 - scheduleWithFixedDelay3.2 固定速率 - scheduleWithFixedDelay 4. 小结 1. 概要 前三篇文章的地址&#xff1a; 定时/延时任务-自己实现一个简单的定时器定时/延时任…...

自编码器(一)

其实自编码器也可以算是自监督学习的一环&#xff0c;因 此我们可以再简单回顾一下自监督学习的框架。如图1.1所示&#xff0c;首先你有大量的没有标注的 数据&#xff0c;用这些没有标注的数据&#xff0c;你可以去训练一个模型&#xff0c;你必须设计一些不需要标注数据的 任…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

Java后端检查空条件查询

通过抛出运行异常&#xff1a;throw new RuntimeException("请输入查询条件&#xff01;");BranchWarehouseServiceImpl.java // 查询试剂交易&#xff08;入库/出库&#xff09;记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势

一、WebRTC与智能硬件整合趋势​ 随着物联网和实时通信需求的爆发式增长&#xff0c;WebRTC作为开源实时通信技术&#xff0c;为浏览器与移动应用提供免插件的音视频通信能力&#xff0c;在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能&#xff0c;对实时…...

Python 解释器安装全攻略(适用于 Linux / Windows / macOS)

目录 一、Windows安装Python解释器1.1 下载并安装Python解释1.2 测试安装是否成功1.3 设置pip的国内镜像------永久配置 二、macOS安装Python解释器三、Linux下安装Python解释器3.1 Rocky8.10/Rocky9.5安装Python解释器3.2 Ubuntu2204/Ubuntu2404安装Python解释器3.3 设置pip的…...