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

【一刷《剑指Offer》】面试题 3:二维数组中的查找

 力扣对应题目链接:240. 搜索二维矩阵 II - 力扣(LeetCode)  

核心考点:数组相关,特性观察,时间复杂度把握。


一、《剑指Offer》对应内容


二、分析题目

  1. 正常查找的过程本质就是排除的过程,谁排除的效率更高,谁对应查找的效率也就更高。
  2. 如果双循环查找,本质是一次排除一个,效率过低。但采取从右上角 / 左下角进行比较,这样就可以一次排除一行或一列。
  3. 注意临界条件。

三、代码(C++)

1、从右上角开始排查

//从右上角开始排查
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i=0, j=matrix[0].size()-1;while(i<matrix.size() && j>=0){if(matrix[i][j]>target)j--;else if(matrix[i][j]<target)i++;else return true;}return false;}
};

注意:本题因为所提供数据范围为:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300

所以,排除了空数组的情况,否则还需要在开头进行特判。

例如,下面这道题目:LCR 121. 寻找目标值 - 二维数组 - 力扣(LeetCode)

//从右上角开始排查
class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {if(plants.size()==0 || plants[0].size()==0) return false;int i=0, j=plants[0].size()-1;while(i<plants.size() && j>=0){if(plants[i][j]>target)j--;else if(plants[i][j]<target)i++;else return true;}return false;}
};

注意:如果采用第二种方法:“从左下角开始排查”,则不需要进行特判,因为如果数组为空,第二种方法并不会进入到循环当中。

//从左下角开始排查
class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {int i=plants.size()-1, j=0;while(i>=0 && j<plants[0].size()){if(plants[i][j]>target)i--;else if(plants[i][j]<target)j++;else return true;}return false;}
};

2、从左下角开始排查

//从左下角开始排查
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int i=matrix.size()-1, j=0;while(i>=0 && j<matrix[0].size()){if(matrix[i][j]>target)i--;else if(matrix[i][j]<target)j++;else return true;}return false;}
};

相关文章:

【一刷《剑指Offer》】面试题 3:二维数组中的查找

力扣对应题目链接&#xff1a;240. 搜索二维矩阵 II - 力扣&#xff08;LeetCode&#xff09; 核心考点&#xff1a;数组相关&#xff0c;特性观察&#xff0c;时间复杂度把握。 一、《剑指Offer》对应内容 二、分析题目 正常查找的过程本质就是排除的过程&#xff0c;谁排除…...

Linux下静态库与动态库使用总结

区别 使用静态库占用的磁盘空间相对比动态库要大。 如果多个可执行程序使用库中同一个函数&#xff0c;那么链接静态库时同一个函数的代码会被复制多份&#xff0c;而链接动态库只复制一份。动态库可共享且版本更新方便 静态链接库在程序编译的时候就被加载进来&#xff0c;不…...

分布式任务调度:架构、原理与实践

引言 在当今快速发展的科技领域中&#xff0c;任务调度作为管理和优化计算资源的重要工具&#xff0c;扮演着至关重要的角色。从单机环境到分布式系统&#xff0c;任务调度的演进不仅跟随着计算机技术的进步&#xff0c;更是为了应对日益复杂的应用场景和需求。本博客将深入探…...

ping命令返回无法访问目标主机和请求超时浅析

在日常经常用ping命令测试网络是否通信正常&#xff0c;使用ping命令时也经常会遇到这两种情况&#xff0c;那么表示网络出现了问题。 1、请求超时的原因 可以看到“请求超时”没有收到任何回复。要知道&#xff0c;IP数据报是有生存时间的&#xff0c;当其生存时间为零时就会…...

地球上的七大洲介绍

地球上的七大洲示意图&#xff1a; 1. 亚洲&#xff08;Asia&#xff09;&#xff1a;世界上最大的洲&#xff0c;面积约为44579000平方公里。亚洲地域辽阔&#xff0c;包括从北极圈到赤道的各种气候和地形。它拥有世界上最多的人口&#xff0c;也是世界上一些最古老文明的发源…...

IntelliJ IDEA 2024 for Mac/Win:引领Java开发新纪元的高效集成环境

在日新月异的软件开发领域&#xff0c;一款高效、智能的集成开发环境&#xff08;IDE&#xff09;无疑是程序员们不可或缺的神兵利器。今天&#xff0c;我要为大家介绍的&#xff0c;正是这样一款集大成之作——IntelliJ IDEA 2024。无论是Mac用户还是Windows用户&#xff0c;只…...

Java 中命令模式,请用代码具体举例

在Java中&#xff0c;命令模式是一种行为设计模式&#xff0c;它允许将请求封装成一个对象&#xff0c;从而使得可以参数化其他对象对请求进行调用、队列化请求、或者记录请求日志&#xff0c;同时支持可撤销的操作。 下面是一个简单的示例代码&#xff0c;展示了如何使用命令模…...

低延时+高并发+强事务丨DolphinDB 交易型内存存储引擎 IMOLTP 使用指南

1. 背景 在一些数据库应用场景中&#xff0c;例如金融行业的交易系统&#xff0c;其主要工作负载来源于对关系表的高频度、高并发的更新和查询操作。这样的应用场景要求数据的读写和计算能够具有低延迟、高并发的特征&#xff0c;同时保证极高的数据一致性&#xff0c;并提供 …...

写代码的修养

看山是山&#xff0c;看水是水 此境界 对业务的思考是浅层的&#xff0c;代码写的不通用&#xff0c;扩展性差&#xff0c;表现在无设计模式 看山不是山&#xff0c;看水不是水 此境界 对业务的思考是中层的&#xff0c;代码写的通用&#xff0c;扩展性好&#xff0c;表现为…...

springboot 问题整合

springboot 启动后访问报错 问题&#xff1a;org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): 原因&#xff1a;mybatis 的全局配置文件和 sql 映射文件没有写 解决&#xff1a;在 application.yml 中添加 mybatis 配置 mybatis:# 全局配…...

UNIAPP二维码展示页亮度调至最亮返回恢复进入前亮度

onLoad(params) {let num plus.screen.getBrightness().toString(); //转字符串是要存到stoage中number类型会存储失败plus.storage.setItem("pmld", num)plus.screen.setBrightness(1); //设置屏幕亮度&#xff0c;范围0-1 }onUnload() {let platformuni.getSystem…...

Golang ProtoBuf 初学者完整教程:安装

一、Protobuf 特点 更高效&#xff1a;使用二进制编码&#xff0c;相比XML/JSON更加高效 跨语言支持&#xff1a;Protobuf 在 .proto 定义需要处理的结构化数据&#xff0c;可以通过 protoc 工具&#xff0c;将 .proto 文件转换为 C、C、Golang、Java、Python 等多种语言的代…...

Isolation Forest 简介

1. 简介 孤立森林 iForest(Isolation Forest)是一种无监督学习算法&#xff0c;用于识别异常值。其基本原理是&#xff1a;异常数据由于数量较少且与正常数据差异较大&#xff0c;因此在被隔离时需要较少的步骤。 两个假设&#xff1a; 1. 异常的值是非常少的(如果异常值很多&…...

Java爬虫携带sign签名

站点&#xff1a;https://www.mytokencap.com/ 代码分析先不写了&#xff0c;大家自行解决&#xff0c;贴代码 1、业务请求设计 public static void md5Pro() {String url "https://api.mytokenapi.com/ticker/currencylistforall";Map<String, String> he…...

设计者模式之中介者模式(下)

3&#xff09;中介者与同事类的扩展 1.结构图 新增了具体同事类Label和具体中介者类SubConcreteMediator。 2.代码实现 //文本标签类&#xff1a;具体同事类 public class Label extends Component {public void update() {System.out.println("文本标签内容改变&#…...

SAP SD学习笔记04 - 出荷Plant(交货工厂),出荷Point(装运点),输送计划,品目的可用性检查,一括纳入/分割纳入,仓库管理

上一章讲了SD的主数据。 SAP SD学习笔记03 - SD模块中的主数据-CSDN博客 本章讲出荷Plant&#xff08;交货工厂&#xff09;&#xff0c;出荷Point&#xff08;装运点&#xff09;和出和路线。 还是偏理论多一些&#xff0c;后面的文章尽量多加些练习巩固一下。 1&#xff0…...

bind包装器——C++新特性(三)

文章目录 bindbind函数模板的原型bind 包装器的用途其他使用示例 &#x1f396; 博主的CSDN主页&#xff1a;Ryan.Alaskan Malamute &#x1f4dc; 博主的代码仓库主页 [ Gitee ]&#xff1a;ryanala [GitHub]&#xff1a; Ryan-Ala bind bind也是一种函数包装器&#xf…...

MXNet的下载安装及问题处理

1、MXNet介绍&#xff1a; MXNet是一个开源的深度学习框架&#xff0c;以其灵活性和效率著称&#xff0c;支持多种编程接口&#xff0c;包括Python、C、R、Julia、Scala等。MXNet支持大规模分布式训练&#xff0c;同时兼顾CPU和GPU的计算资源&#xff0c;尤其擅长于模型并行和数…...

Python 中的列表排序和排序规则

Python 中的列表排序和排序规则 在 Python 中&#xff0c;列表的排序是一个常见的操作&#xff0c;可以使用内置函数 sorted() 或列表对象的 sort() 方法来完成。下面将介绍这两种方法以及排序规则的使用方式。 1. 使用 sorted() 函数排序列表&#xff08;临时性排序&#xf…...

面经整理1

感觉好几个都是backtracking Letter Combinations of a Phone Number - LeetCode 典型的backtracking&#xff0c;注意String的处理 class Solution {String[] keyboard new String[]{"", "", "abc","def","ghi","…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

无需布线的革命:电力载波技术赋能楼宇自控系统-亚川科技

无需布线的革命&#xff1a;电力载波技术赋能楼宇自控系统 在楼宇自动化领域&#xff0c;传统控制系统依赖复杂的专用通信线路&#xff0c;不仅施工成本高昂&#xff0c;后期维护和扩展也极为不便。电力载波技术&#xff08;PLC&#xff09;的突破性应用&#xff0c;彻底改变了…...

C# WPF 左右布局实现学习笔记(1)

开发流程视频&#xff1a; https://www.youtube.com/watch?vCkHyDYeImjY&ab_channelC%23DesignPro Git源码&#xff1a; GitHub - CSharpDesignPro/Page-Navigation-using-MVVM: WPF - Page Navigation using MVVM 1. 新建工程 新建WPF应用&#xff08;.NET Framework) 2.…...

【工具教程】多个条形码识别用条码内容对图片重命名,批量PDF条形码识别后用条码内容批量改名,使用教程及注意事项

一、条形码识别改名使用教程 打开软件并选择处理模式&#xff1a;打开软件后&#xff0c;根据要处理的文件类型&#xff0c;选择 “图片识别模式” 或 “PDF 识别模式”。如果是处理包含条形码的 PDF 文件&#xff0c;就选择 “PDF 识别模式”&#xff1b;若是处理图片文件&…...