算法:数组常见套路1---双指针、取模、打擂台法
文章来源:
https://blog.csdn.net/weixin_45630258/article/details/132738318
欢迎各位大佬指点、三连
一、数组的合并–双指针[快慢指针]
1、题目:
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
- 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
2、分析特点:
两个数组已经被排序
,相当于两条有序的队列,非递减,从小到大排队,每次都从两条队伍中取走最小的那个数放到结果中。
3、代码:
4、复杂度分析:
时间复杂度:O(m+n)O(m+n)O(m+n)。 指针移动单调递增,最多移动 m+nm+nm+n 次,因此时间复杂度为 O(m+n)O(m+n)O(m+n)。
空间复杂度:O(m+n)O(m+n)O(m+n)。 需要建立长度为 m+nm+nm+n 的中间数组 sorted。
5、总结:
本题比较简单,只需要抓住,有序递增的两个数组,直接当队列,抓最小。当然更简单的是直接把其中一个数组的全部元素存储到另外一个数组后面的空间,然后利用封装好的方法排序即可,即 Arrays.sort() 方法
二、数组的删除–双指针[快慢指针]
1、题目:
给你一个数组 nums和一个值 val,你需要原地移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
2、分析特点:
- 题目要求:原地移除
- 移除所有val的元素,则
结果数组一定比原数组的长度更短
。要求原地移除 >我们可以把结果数组直接写在原数组上
,并且结果数组是那些非等于val的元素组成的,从位置0开始,到某个位置作为结果数组,而原数组需要从0开始到整个数组的长度进行遍历> 使用双指针。 - 结果数组的指针:[0, left], 结果数组的目的是收集起来结果,他是left一步步进行加加的。
- 原数组的指针:[0, right],right <= 原数组长度,right 是用于指向原数组当前的元素是否不会等于val,可以被收集。
3、代码:
4、复杂度分析:
时间复杂度:O(n)O(n)O(n),其中 nnn 为序列的长度。我们只需要遍历该序列至多两次。
空间复杂度:O(1)O(1)O(1)。我们只需要常数的空间保存若干变量。
5、总结:
本题比较简单,只需要抓住,题意要求:原地移除,原地==>结果只能输出到原数组上面,移除,则结果数组长度比原数组更短。利用结果数组从0,开始left++进行收集,而原数组使用right指针从0开始遍历,判断当前元素是否可以被收集起来。
==> 目的就是收集所有符合条件的元素。
三、数组的轮询–取模
1、题目:
给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
2、分析特点:
-
轮转 ==> 取模运算
-
我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度,我们遍历原数组,将原数组下标为 i 的元素放至新数组下标为 (i+k) mod n 的位置,最后将新数组拷贝至原数组即可。
3、代码:
4、复杂度分析:
- 时间复杂度: O(n),其中 n 为数组的长度。
- 空间复杂度: O(n)。
5、总结:
轮转、循环 k 步,要想到取模运算,另外需要一个新数组作为结果数组是因为如果我们不使用额外数组,我们直接将每个数字放至它最后的位置,这样被放置位置的元素会被覆盖从而丢失,所以需要一个新数组作为结果数组,最后拷贝回去原数组。
四、数组的最大差值–打擂台法
1、题目:
给定一个整数数组 nums,找出给定数组中两个数字之间的最大差值。要求,第二个数字必须大于第一个数字。
2、分析特点:
求最大差值 ==> 最大值 - 最小值
- 只需要遍历价格数组一遍,记录历史最小值,非最小值的考虑是最大值。
3、代码:
4、复杂度分析:
- 时间复杂度:O(n),只需要遍历一次。
- 空间复杂度:O(1),只使用了常数个变量。
5、总结:
使用打擂台的思想,遍历的时候,考虑当前值是最小值,则记录最小值,否则考虑当前值是最大值,进行更新。
如果本文对你有帮助的话记得给一乐点个赞哦,感谢!
相关文章:

算法:数组常见套路1---双指针、取模、打擂台法
文章来源: https://blog.csdn.net/weixin_45630258/article/details/132738318 欢迎各位大佬指点、三连 一、数组的合并–双指针[快慢指针] 1、题目: 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ࿰…...
App 出海实践:Google Play 结算系统
作者:业志陈 现如今,App 出海热度不减,是很多公司和个人开发者选择的一个市场方向。App 为了实现盈利,除了接入广告这种最常见的变现方式外,就是通过提供各类虚拟商品或者是会员服务来吸引用户付费了,此时 …...

国际慈善日 | 追寻大爱无疆,拓世科技集团的公益之路
每年的9月5日,是联合国大会正式选定的国际慈善日。这一天的设立,旨在通过提高公众对慈善活动的意识,鼓励慈善公益活动通过各种形式在全球范围内得到增强和发展。这是一个向慈善公益事业致敬的日子,同时也是呼吁全球团结一致共同发…...
关于DNS的一些认识
目录 什么是DNS? 一台具有单个DNS的机器可以拥有多个地址吗? 一台计算机可以有多个属于不同顶级域的DNS名字吗? 什么是DNS? DNS是域名系统(Domain Name System)的缩写,它是互联网中用于将域名…...
游戏性能优化
Unity性能优化主要包括以下方面: 1.渲染性能 。包括减少Draw Calls、减少三角面数、使用LOD、使用批处理技术、减少实时光源等,以提高游戏的帧率和渲染效率。 2.内存性能 。包括使用对象池、使用合适的纹理、使用异步加载资源等,以减少内存占…...

公开游戏、基于有向图的游戏
目录 〇,背景 一,公开游戏、策梅洛定理 1,公开游戏 2,策梅洛定理 二,有向图游戏 1,狭义有向图游戏 2,广义有向图游戏 3,狭义有向图游戏的SG数 4,Bash Game 力扣…...

CSS学习笔记05
CSS笔记05 定位 position CSS 属性position - 用于指定一个元素在文档中的定位方式。top,right,bottom 和 left 属性则决定了该元素的最终位置。position 有以下常用的属性值: position: static; - 默认值。指定元素使用正常的布局行为&am…...
Linux查看指定端口是否被占用
在Linux中,可以使用多种方法来检查一个特定端口(例如3306,通常由MySQL使用)是否被占用: 使用netstat命令: 如果系统中已安装了netstat,可以使用以下命令检查3306端口: netstat -tuln | grep 330…...

【Python 自动化】小说推文一键生成思路概述
最近看了一下小说推文成品软件的思路,发现可以完全迁移到我的 BookerAutoVideo 上面来。这篇短文里面,我试着分析一下整个推文视频生成的流程,以及简要阐述一下有什么工具。 整体流程是这样: 分句 原文是按照段落组织的…...
MySQL中的字符集与排序规则详解
在 MySQL 中,字符集(Character Set)用于确定可以在数据库中存储的字符集合,而排序规则(Collation)用于指定比较和排序字符串的规则。下面是关于 MySQL 中字符集和排序规则的一些详细信息: 字符集…...

Java中如何进行加锁??
笔者在上篇文章介绍了线程安全的问题,接下来本篇文章就是来讲解如何避免线程安全问题~~ 前言:创建两个线程,每个线程都实现对同一个变量count各自自增5W次,我们来看一下代码: class Counter{private int count0;publi…...

Pytorch3D多角度渲染.obj模型
3D理解在从自动驾驶汽车和自主机器人到虚拟现实和增强现实的众多应用中发挥着至关重要的作用。在过去的一年里,PyTorch3D已经成为一个越来越流行的开源框架,用于使用Python进行3D深度学习。值得庆幸的是,PyTorch3D 库背后的人员已经完成了实现…...

MyBatisPlus 基础Mapperr接口:增删改查
MyBatisPlus 基础Mapper接口:增删改查 插入一条数据 代码 Testpublic void insert() {User user new User();user.setId(6L);user.setName("张三");user.setAge(25);user.setEmail("zhangsanexample.com");userMapper.insert(user);}日志 数…...

计算机网络与技术——概述
😊计算机网络与技术——概述 👻前言🥏信息时代下计算机网络的发展🌏互联网概述📡计算机网络基本概念📡互联网发展三阶段📡互联网的标准化 🌏互联网的组成📡互联网的边缘部…...
详解TCP/IP协议第三篇:通信数据在OSI通信模型的上下传输
文章目录 一:OSI通信模型间数据传输展示 二:应用层到会话层解析 1:应用层 2:表现层 3:会话层...

《C++ primer plus》精炼(OOP部分)——对象和类(2)
“学习是人类成长的喷泉。” - 亚里士多德 文章目录 内联函数对象的方法和属性构造函数和析构函数构造函数的种类使用构造函数析构函数列表初始化 const成员函数this指针对象数组类作用域作用域为类的常量类作用域内的枚举 内联函数 定义位于类声明中的函数自动成为内联函数。…...

一点感受
做了两天企业数字化转型的评委,涉及全国最顶级的公司、最顶级的实际落地项目案例,由企业真实的落地团队亲自当面讲解。主要是为了了解了解真实的一线、真实的客户、真实的应用现状和应用水平。 (1)现状 我评审的涉及底层技术平台&…...

VirtualBox RockyLinux9 网络连接
有几次都是隔一段时间之后启动虚拟机,用第三方ssh工具就连接不上了。 简单记录一下。 1、VirtualBox设置 2、IP设置 cd /etc/NetworkManager/system-connections/ vim enp0s3.nmconnection[connection] idenp0s3 uuid9c404b41-4636-397c-8feb-5c2ed38ef404 typeet…...
java 实现适配器模式
适配器模式(Adapter Pattern)是一种结构型设计模式,用于将一个类的接口转换成另一个类的接口,使得原本不兼容的类可以协同工作。适配器模式包括两种类型:类适配器和对象适配器。下面分别介绍这两种类型的实现方式。 类…...
后端常用的Linux命令大全
后端常用的Linux命令大全 基础常用命令 Sudo Command 该命令是“superuser do”的缩写。sudo 是最常用的命令之一,可让你执行需要管理或 root 特权和权限的任务。 使用sudo命令时系统会提示用户重新使用密码进行身份验证。接下来,Linux 系统将记录一…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...

手机平板能效生态设计指令EU 2023/1670标准解读
手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读,综合法规核心要求、最新修正及企业合规要点: 一、法规背景与目标 生效与强制时间 发布于2023年8月31日(OJ公报&…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...