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

数组(一)-- LeetCode[26][80] 删除有序数组中的重复元素

1 删除有序数组中的重复项

1.1 题目描述

        给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致

        由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。

        将最终结果插入 nums 的前 k 个位置后返回 k 。

        不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2:
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

1.2 思路分析

        已知数组 nums 是有序的,而且我们只能在原地修改 nums 数组,不能创建新的数组空间来存储删除重复出现的元素后的结果。我们需要一边遍历数组查找相同元素,一边在对比发现不同元素时修改数组元素,那么我们可以考虑双指针法的快慢指针了,定义 p 和 q 作为指针,初始化时指针 p 指向数组的起始位置(nums[0]),指针 q 指向指针 p 的后一个位置(nums[1])。随着指针 q 不断向后移动,将指针 q 指向的元素与指 p 指向的元素进行比较:

  • 如果nums[q] ≠ nums[p],那么nums[p + 1] = nums[q];
  • 如果nums[q] = nums[p],那么指针q继续向后查找;

图示:

1.3 代码实现

class Solution:def removeDuplicates(self, nums: List[int]) -> int:p, q = 0, 1while q < len(nums):if nums[q] != nums[p]:p += 1nums[p] = nums[q]q += 1return p + 1

        复杂度分析:时间复杂度:O(n)O(n)O(n)。 空间复杂度:O(1)O(1)O(1)

        进一步优化:

        考虑如下数组:

        此时数组中没有重复元素,按照上面的方法,每次比较时 nums[p] 都不等于 nums[q],因此就会将 q 指向的元素原地复制一遍,这个操作其实是不必要的。

        因此我们可以添加一个小判断,当 q - p > 1 时,才进行复制。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:p, q = 0, 1while q < len(nums):if nums[q] != nums[p]:if q - p > 1:nums[p+1] = nums[q]p += 1q += 1return p + 1

2 删除有序数组中的重复项 II

        给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。

        不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:
输入:nums = [1,1,1,2,2,3]
输出:5, nums = [1,1,2,2,3]
解释:函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2:
输入:nums = [0,0,1,1,1,1,2,3,3]
输出:7, nums = [0,0,1,1,2,3,3]
解释:函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

        思路和上面的类似,改变的地方是:初始化时指针 p 指向数组的起始位置(nums[1]),指针 q 指向指针 p 的后一个位置(nums[2])。随着指针 q 不断向后移动,将指针 q 指向的元素与指 p 指向的元素进行比较:

  • 如果nums[q] ≠ nums[p-1],那么nums[p + 1] = nums[q];
  • 如果nums[q] = nums[p],那么指针q继续向后查找;
```python
class Solution:def removeDuplicates(self, nums: List[int]) -> int:p, q = 1, 2while q < len(nums):if nums[q] != nums[p-1]:p += 1nums[p] = nums[q]q += 1return p + 1

通用解法:
        为了让解法更具有一般性,我们将原问题的「最多保留 1 位」修改为「最多保留 k 位」。
对于此类问题,我们应该进行如下考虑:

  • 由于是保留 k 个相同数字,对于前 k 个数字,我们可以直接保留。
  • 对于后面的任意数字,能够保留的前提是:与当前写入的位置前面的第 k 个元素进行比较,不相同则保留。

        此时,初始化时指针 p 指向数组的起始位置(nums[k-1]),指针 q 指向指针 p 的后一个位置(nums[k])。随着指针 q 不断向后移动,将指针 q 指向的元素与指 p 指向的元素进行比较:

  • 如果nums[q] ≠ nums[p-k+1],那么nums[p + 1] = nums[q];
  • 如果nums[q] = nums[p],那么指针q继续向后查找;

相关文章:

数组(一)-- LeetCode[26][80] 删除有序数组中的重复元素

1 删除有序数组中的重复项 1.1 题目描述 给你一个 升序排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次&#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度&#xff0c…...

GEE学习笔记 六十三:新的地图图层ui.Map.CloudStorageLayer

在GEE中导出数据有一种方式是直接导出地图到Google Cloud Storage中&#xff0c;也就是Export.map.toCloudStorage(xxx)&#xff0c;这种方式是将我们计算生成影像导出成为静态瓦片的格式存放在Google Cloud Storage中。我们可以在其他的前端程序比如OpenLayer、Mapbox GL JS等…...

ClickHouse 语法详解

ClickHouse有2类解析器&#xff1a;完整SQL解析器&#xff08;递归式解析器&#xff09;&#xff0c;以及数据格式解析器&#xff08;快速流式解析器&#xff09; 除了 INSERT 查询&#xff0c;其它情况下仅使用完整SQL解析器。 INSERT查询会同时使用2种解析器&#xff1a;INSE…...

手把手教你将微信小程序放到git上

背景 首先&#xff0c;要创建一个自己的git仓库&#xff0c;这里默认大家都能够自己创建了git仓库了。如果不会创建仓库的话&#xff0c;百度一下&#xff0c;很容易就能够创建了&#xff01;&#xff08;后续&#xff0c;如有不知道在哪里&#xff0c;怎么创建仓库的话&#…...

功能测试3年,回顾一路走来的艰辛

不论你是什么时候开始接触测试这个行业的&#xff0c;你首先听说的应该是功能测试。通过一些测试手段来验证开发做出的代码是否符合产品的需求&#xff1f;当然你也有自己对功能测试的理解&#xff0c;但是最近两年感觉功能测试好像不太受欢迎&#xff0c;同时不少同学真的是功…...

作为Linux C/C++程序员必备的工具

Linux系统 可以选择centOS或者ubautu server(不建议选择桌面版本的)。不建议裸机安装&#xff0c;玩坏了就特别麻烦。不建议使用有桌面版本的ubautu&#xff0c;在一定程度有桌面的版本的会消耗性能。 如果经济实力允许&#xff0c;可以购买云服务器。 参考文章: Ubuntu server…...

docker Alpine一个只有5M小而美的Docker镜像

docker Alpine一个只有5M小而美的Docker镜像 参考链接: Alpine 一个只有5M的Docker镜像 http://www.infoq.com/cn/news/2016/01/Alpine-Linux-5M-Docker?utm_sourcetuicool&utm_mediumreferral 使用alpinelinux 构建 golang http 启动了才15mb http://blog.csdn.net/fre…...

Springboot扩展点之InstantiationAwareBeanPostProcessor

Springboot扩展点系列实现方式、工作原理集合&#xff1a;Springboot扩展点之ApplicationContextInitializerSpringboot扩展点之BeanFactoryPostProcessorSpringboot扩展点之BeanDefinitionRegistryPostProcessorSpringboot扩展点之BeanPostProcessorSpringboot扩展点之Instant…...

基于 U-Net 网络的遥感图像语义分割 完整代码+论文

一、研究目的U-Net 是一种由全卷积神经网络启发的对称结构网络&#xff0c;在医疗影像分割领域取得了很好的效果。 此次研究尝试使用 U-Net 网络在对多光谱遥感影像数据集上进行训练&#xff0c;尝试使用卷积神经网络自动分割出建筑&#xff0c;希望能够得到一种自动分割遥感影…...

Codeql 编译Shiro1.2.4爬坑

0x00 前言 这个Codeql一定要编译才能生成Database&#xff0c;是真的比较恼火&#xff0c;很多项目都不一定可以生成&#xff0c;环境就是一个非常大的坑&#xff0c;为了防止以后&#xff0c;所以将shiro1.2.4编译过程进行记录。 0x01 正文 首先是需要下载到shiro1.2.4的源…...

新C++(9):谈谈,翻转那些事儿

"相信羁绊&#xff0c;相信微光&#xff0c;相信一切无常。"一、AVL树翻转那些事儿(1)什么是AVL树&#xff1f;在计算机科学中&#xff0c;AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1&#xff0c;所以它也被称为高度平衡树。…...

Java深克隆的几种方式

目录 1、通过继承Cloneable接口&#xff0c;重写clone方法实现深克隆 2、通过序列化与反序列化的方式实现深克隆 3、第三方工具类实现深克隆&#xff0c;克隆对象需继承Serializable接口 3.1、Apache Commons Lang的SerializationUtils.clone方法 3.2、Gson工具类 3.3、F…...

PointNet++的源码运行

首先&#xff0c;从github上下载源码https://github.com/yanx27/Pointnet_Pointnet2_pytorch也可以从百度网盘下载链接&#xff1a;https://pan.baidu.com/s/1sgTYuqnBVC9p3bib450SOQ 提取码&#xff1a;gujd再下载对应的测试数据分类数据modelnet40_normal_resampled下载&…...

npm 上传自己的包

mkdir demo 创建一个新的文件夹 npm init 初始化项目 生成一个package.json文件 name version description等等touch index.js 创建一个node 可执行脚本新的js 文件 #!/usr/bin/env node // 必须在文件头加如上内容指定运行环境为node console.log(hello cli)在package.json 中…...

【Linux】常用命令大全(二)

目录 4. Linux常用命令 4.1 Linux命令初体验 4.2 文件目录操作命令 4.3 拷贝移动命令 4.4 打包压缩命令 4.5 文本编辑命令 4.6 查找命令 4. Linux常用命令 4.1 Linux命令初体验 4.1.1 常用命令演示 在这一部分中&#xff0c;我们主要介绍几个常用的命令&#xff0c…...

第一章 操作系统概述

目录一、什么是操作系统&#xff1f;1、操作系统的概念2、计算系统的构成3、主要作用二、操作系统有哪些功能&#xff1f;1、操作系统的目标2、操作系统的功能三、操作系统有哪些特征&#xff1f;1、并发性2、共享性3、虚拟性4、异步性四、操作系统的运行机制是怎样的&#xff…...

ChatGPT为什么不受开发者喜欢?

记得 ChatGPT 最开始上线不久的时候&#xff0c;看到的大部分尝鲜和测试结果都是开发者在做进行敲代码测试&#xff0c;可以说职业危机感非常强的一群人了。 再者&#xff0c;加上 ChatGPT 要使用起来其实是有一些技术门槛的&#xff0c;愿意折腾的人也多是程序员&#xff0c;…...

Lua table

Table&#xff08;表&#xff09; table 是 lua 中唯一的数据结构&#xff0c;可以用于表示 数组&#xff0c;字典与结构体。它非常强大&#xff0c;可以储存任何数据类型。 table 的数据单元为一对键值。 table 是不固定大小的&#xff0c;你可以根据自己需要进行扩容。 构…...

JavaScript:使用for in不是一个很好的抉择

for in 如果让你遍历对象中的key和value&#xff0c;你第一个想到的一定是使用for in const o{name:"chengqige",age:23 } for (let key in o){console.log(key,o[key]); }看起来是没有问题的&#xff0c;但是如果我在下面加一行代码&#xff0c;输出的结果就可能让…...

Go语言学习小笔记(一)

Go语言学习小笔记&#xff08;一&#xff09; 入口 项目的主入口&#xff1a;一般在main.go 包导入 一个包定义一组编译过的代码&#xff0c;包的名字类似命名空间&#xff0c;可以用来间接访问包内声明的标识符 所有处于同一个文件夹中的代码文件&#xff0c;必须使用同一…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

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

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

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...