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

剑指offer -- 二维数组中的查找

二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)

暴力查找法:

是一种简单直接的解决方法,可以用于在二维数组中查找目标值。该方法的思路是遍历数组的每个元素,逐个与目标值进行比较。

具体步骤如下:

  1. 从数组的第一行第一列开始,逐行逐列地遍历数组的每个元素。
  2. 对于当前遍历到的元素,与目标值进行比较:
    • 如果当前元素等于目标值,则找到目标值,返回true。
    • 如果当前元素大于目标值,则可以提前结束查找,因为数组已经按递增顺序排列,后续元素必定更大。
  3. 如果遍历完整个数组都没有找到目标值,则说明目标值不存在于数组中,返回false。
  4.  时间复杂度为O(m * n)
bool searchMatrix(vector<vector<int>>& matrix, int target) {for (int i = 0; i < matrix.size(); i++) {for (int j = 0; j < matrix[i].size(); j++) {if (matrix[i][j] == target) {return true;  // 找到目标值} else if (matrix[i][j] > target) {return false;  // 提前结束查找}}}return false;  // 目标值不存在于数组中
}

 

对于有序的二维数组,我们可以利用二分查找法进行查找目标值。

算法步骤:
1. 初始化指针,将左上角的元素作为起始点,将右下角的元素作为终止点。初始时,起始点为数组的左上角元素,终止点为数组的右下角元素。
2. 在每一次迭代中,将搜索区域一分为二,找到中间元素(可以选择行中间或列中间的元素)。
3. 将目标值与中间元素进行比较:
   - 如果中间元素等于目标值,则找到目标值,返回true。
   - 如果中间元素大于目标值,则目标值可能在中间元素的左侧或上方,将搜索区域缩小为左上方的子区域,即终止点变为中间元素的左上方元素。
   - 如果中间元素小于目标值,则目标值可能在中间元素的右侧或下方,将搜索区域缩小为右下方的子区域,即起始点变为中间元素的右下方元素。
4. 重复执行步骤2和步骤3,直到找到目标值或搜索区域为空(起始点超过终止点)为止。
5. 如果最终搜索区域为空,说明目标值不存在于数组中,返回false。

6.时间复杂度(cols*log(rows))

bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty() || matrix[0].empty()) {return false;  // 处理空数组的情况}int rows = matrix.size();int cols = matrix[0].size();int left = 0;int right = rows * cols - 1;while (left <= right) {int mid = left + (right - left) / 2;int midValue = matrix[mid / cols][mid % cols];if (midValue == target) {return true;  // 找到目标值} else if (midValue < target) {left = mid + 1;  // 目标值可能在中间元素的右侧或下方} else {right = mid - 1;  // 目标值可能在中间元素的左侧或上方}}return false;  // 目标值不存在于数组中
}

 

题目要求在一个二维数组中查找是否存在某个整数。该二维数组的特点是每一行从左到右递增,每一列从上到下递增。

解决该问题的一个思路是从二维数组的右上角开始比较,根据目标值与当前元素的大小关系,可以逐步缩小查找范围。具体步骤如下:

  1. 初始化指针row为0,指向第一行的最后一个元素,指针col为二维数组的列数减1,指向最后一列的第一个元素。
  2. 进入循环,比较当前指针指向的元素array[row][col]与目标值target的大小关系:
    • 如果array[row][col]等于target,说明找到了目标值,返回True
    • 如果array[row][col]大于target,说明目标值可能在当前元素的左侧,将指针col向左移动一列。
    • 如果array[row][col]小于target,说明目标值可能在当前元素的下方,将指针row向下移动一行。
  3. 如果指针rowcol超出了二维数组的边界,则说明查找范围已经越界,目标值不存在于二维数组中,返回False
  4. 空间复杂度O(m+n)
#include <iostream>
#include <vector>using namespace std;bool findTarget(vector<vector<int>>& array, int target) {if (array.empty() || array[0].empty()) {return false;}int rows = array.size();int cols = array[0].size();int row = 0;int col = cols - 1;while (row < rows && col >= 0) {if (array[row][col] == target) {return true;} else if (array[row][col] > target) {col--;} else {row++;}}return false;
}int main() {vector<vector<int>> array = {{1, 2, 8, 9},{2, 4, 9, 12},{4, 7, 10, 13},{6, 8, 11, 15}};int target1 = 7;int target2 = 3;cout << boolalpha << findTarget(array, target1) << endl;  // 输出: truecout << boolalpha << findTarget(array, target2) << endl;  // 输出: falsereturn 0;
}

相关文章:

剑指offer -- 二维数组中的查找

二维数组中的查找_牛客题霸_牛客网 (nowcoder.com) 暴力查找法: 是一种简单直接的解决方法&#xff0c;可以用于在二维数组中查找目标值。该方法的思路是遍历数组的每个元素&#xff0c;逐个与目标值进行比较。 具体步骤如下&#xff1a; 从数组的第一行第一列开始&#xff0c;…...

3. 自然语言处理NLP:具体用途(近义词类比词;情感分类;机器翻译)

一、求近义词和类比词 1. 近义词 方法一&#xff1a;在嵌入模型后&#xff0c;可以根据两个词向量的余弦相似度表示词与词之间在语义上的相似度。 方法二&#xff1a;KNN&#xff08;K近邻&#xff09; 2. 类比词 使用预训练词向量求词与词之间的类比关系。eg&#xff1a;man&a…...

Hibernate的FlushMode

一、Session中FlushMode的设置&#xff1a; 在事务开启前设置FlushMode属性&#xff0c;方法: // session.setFlushMode(FlushMode.Always|AUTO|COMMIT|NEVER|MANUAL)。Service public class TestService {Logger log LoggerFactory.getLogger(getClass());AutowiredEntityM…...

二线程序员的出路

最近长沙不太平。去年被动离职一拨人之后&#xff0c;HR一直强调降本增效&#xff0c;人人自危&#xff0c;挤走一拨人&#xff0c;反正会有大量内卷失败的一线程序员进来填坑。当然留就有人走&#xff0c;前同事除了几个出去搞培训创业&#xff08;后面解散了&#xff09;的之…...

MKS SERVO4257D 闭环步进电机_系列2 菜单说明

第1部分 产品介绍 MKS SERVO 28D/35D/42D/57D 系列闭环步进电机是创客基地为满足市场需求而自主研发的一款产品。具备脉冲接口和RS485/CAN串行接口&#xff0c;支持MODBUS-RTU通讯协议&#xff0c;内置高效FOC矢量算法&#xff0c;采用高精度编码器&#xff0c;通过位置反馈&am…...

使用Actor-Critic的DDPG强化学习算法控制双关节机械臂

在本文中&#xff0c;我们将介绍在 Reacher 环境中训练智能代理控制双关节机械臂&#xff0c;这是一种使用 Unity ML-Agents 工具包开发的基于 Unity 的模拟程序。 我们的目标是高精度的到达目标位置&#xff0c;所以这里我们可以使用专为连续状态和动作空间设计的最先进的Deep…...

黑马学生入职B站1年,晒出21K月薪:我想跳槽华为

现在的Z时代&#xff0c;嘴上说着不要&#xff0c;身体却很诚实。 前两天&#xff0c;黑马发布了《2022年度互联网平均薪资出炉&#xff01;高到离谱&#xff01;》&#xff0c;信息传输、软件和信息技术服务业薪资遥遥领先&#xff01;Z时代举头望着天花板&#xff0c;故作潇…...

一文看懂GPT风口,都有哪些创业机会?

新时代的淘金者&#xff0c;低附加价值的创业要谨慎&#xff0c;高附加价值、低技术门槛创业也要谨慎&#xff0c;主干道边上的创业也要谨慎。不少朋友看完不淡定了&#xff0c;干什么都谨慎&#xff0c;回家躺平好了&#xff0c;我有个朋友&#xff0c;靠ChatGPT&#xff0c;半…...

chatgpt赋能python:Python中的不确定尾数问题

Python中的不确定尾数问题 Python作为一种高级编程语言&#xff0c;被广泛应用于数据科学、机器学习、Web开发等众多领域。然而&#xff0c;Python在处理浮点数时会出现一些不确定尾数的问题&#xff0c;给程序员和数据分析员带来不少麻烦。本篇文章将介绍Python中不确定尾数的…...

杜绝开源依赖风险,许可证扫描让高效合规「两不误」

目录 开源许可证及其常见类型 开源许可证扫描是软件研发过程中&#xff0c;不可或缺的工具 极狐GitLab 开源许可证扫描的优势与应用 Step 1&#xff1a;启用及设置许可证策略 Step 2&#xff1a;自动创建策略文件存放项目 Step 3&#xff1a;查看许可证合规情况 Step 4&…...

【sop】含储能及sop的多时段配网优化模型

目录 1 主要内容 2 部分代码 3 程序结果 4 下载链接 1 主要内容 之前分享了含sop的配电网优化模型&#xff0c;链接含sop的配电网优化,很多同学在咨询如何增加储能约束&#xff0c;并进行多时段的优化&#xff0c;本次拓展该部分功能&#xff0c;在原代码的基础上增加储能模…...

nodjs使用阿里云镜像安装

要使用阿里云镜像来安装 npm 包&#xff0c;你需要按照以下步骤进行操作&#xff1a; 首先&#xff0c;确保你已经安装了 Node.js 和 npm。你可以在终端&#xff08;或命令提示符&#xff09;中输入以下命令来验证它们的安装&#xff1a; node -v npm -v如果显示了 Node.js 和…...

C++ Primer Plus 第二章习题

目录 复习题 1.C程序的模块叫什么&#xff1f; 2.#include 预处理器编译指令的用处&#xff1f; 3.using namespace std; 该语句是干什么用的&#xff1f; 4.什么语句可以打印一个语句"hello,world"&#xff0c;然后重新换行&#xff1f; 5.什么语句可以用来创…...

两分钟学会 制作自己的浏览器 —— 并将 ChatGPT 接入

前期回顾 分享24个强大的HTML属性 —— 建议每位前端工程师都应该掌握_0.活在风浪里的博客-CSDN博客2分享4个HTML5 属性&#xff0c;开发必备https://blog.csdn.net/m0_57904695/article/details/130465836?spm1001.2014.3001.5501 &#x1f44d; 本文专栏&#xff1a;开发…...

HEVC中,mvd怎么写进码流的?

文章目录 Motion vector difference syntax 标准文档描述语义解释设计意义 Motion vector difference syntax 标准文档描述 语义解释 MvdL1[ x0 ][ y0 ][ compIdx ] L1列表的mvd x0,y0 表示亮度快左上角坐标 compIdx 0表示水平 compIdx 0表示垂直 mvd_l1_zero_flag&#xff1a…...

隐形黑客潜入美国和关岛关键基础设施而未被发现

微软和“五眼联盟”国家周三表示&#xff0c;一个隐秘的组织成功地在美国和关岛的关键基础设施组织中建立了一个持久的立足点&#xff0c;而没有被发现。 这家科技巨头的威胁情报团队正在以伏特台风(Volt Typhoon)的名义跟踪这些活动&#xff0c;包括入侵后的凭证访问和网络系…...

设计模式—“接口隔离”

在组件构建过程中,某些接口之间直接的依赖常常会带来很多问题、甚至根本无法实现。采样添加一层间接(稳定)接口,来隔离本来互相紧密关联的接口是一种常见的解决方案。 典型模式有:Fascade、Proxy、Adapter、Mediator 一、Fascade 动机 上述A方案的问题在于组件的客户和…...

【C++学习】异常

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《C学习》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 异常 &#x1f96e;异常&#x1f362;自定义异常体系&#x1f362;C标准库的异常体系&#x1f362;异…...

如何理解TCP是面向字节流协议?

传输层是网络协议中的重要层次之一&#xff0c;主要负责向两个主机中的进程之间的通信提供服务。传输层的主要功能包括复用和分用、流量控制、分段/重组和差错控制。传输层在终端用户之间提供透明的数据传输&#xff0c;向上层提供可靠的数据传输服务。 传输层的复用和分用功能…...

机器学习期末复习 线性模型

1.线性回归&#xff0c;对数几率回归&#xff0c;线性判别分析是分类还是回归任务&#xff1f;是有监督的学习还是无监督的学习&#xff1f; 有监督学习和无监督学习 解释&#xff1a; 线性模型要做的有两类任务&#xff1a;分类任务、回归任务 分类的核心就是求出一条直线w…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...