当前位置: 首页 > 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;你必须设计一些不需要标注数据的 任…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...