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

力扣80、删除有序数组中的重复项Ⅱ(中等)

1 题目描述

图1 题目描述

2 题目解读

        对于有序数组nums,要求在不使用额外数组空间的条件下,删除数组nums中重复出现的元素,使得nums中出现次数超过两次的元素只出现两次。返回删除后数组的新长度。

3 解法一:双指针

        双指针法可以很好地解决此题。

3.1 解题思路

        设置双指针,从数组nums的第3个元素开始比较,直到nums的最后一个元素。

3.2 设计代码

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n <= 2) {return n;}int slow = 2, fast = 2;while (fast < n) {if (nums[slow - 2] != nums[fast]) {nums[slow] = nums[fast];++slow;}++fast;}return slow;}
};
int main() {int x[] = { 1,1,1,2,2,3 };vector<int> nums;for (int i = 0; i < 6; i++){nums.push_back(x[i]);}Solution S;int ans = S.removeDuplicates(nums);cout << ans << endl;return 0;
}

3.3 复杂度分析

  • 时间复杂度:O(n)。while循环遍历了一遍数组元素。
  • 空间复杂度:O(1)。没有使用额外数组空间。

3.4 提交结果

图2 双指针法代码执行结果

4 解法二:前移法

        前移法是由双指针法扩展出来的一种方法,与双指针法有着相似的思想。

4.1 解题思路

        设置指针right,从数组nums的第3个元素开始遍历,使用变量k记录需要移除的元素的个数,将需要移动的元素前移k个位置。

4.2 设计代码

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n <= 2) {return n;}// k累计删除的元素个数int fast = 2, k = 0;while (fast < n) {if (nums[fast - k - 2] != nums[fast]) {nums[fast - k] = nums[fast];}else {++k;}++fast;}return fast - k;}
};
int main() {int x[] = { 1,1,1,2,2,3 };vector<int> nums;for (int i = 0; i < 6; i++){nums.push_back(x[i]);}Solution S;int ans = S.removeDuplicates(nums);cout << ans << endl;return 0;
}

4.3 复杂度分析

  • 时间复杂度:O(n)。while循环遍历了一遍数组nums的元素。
  • 空间复杂度:O(1)。没有使用额外数组空间。

4.4 提交结果

图3 前移法代码执行结果

5 解题心得

  • 让有序数组nums中重复出现的元素只出现两次,是让其只出现一次的变体题目,难度更大。
  • 双指针法与前移法之间,可以相互转换。
  • 双指针法中,left指针用于放置新元素。

相关文章:

力扣80、删除有序数组中的重复项Ⅱ(中等)

1 题目描述 图1 题目描述 2 题目解读 对于有序数组nums&#xff0c;要求在不使用额外数组空间的条件下&#xff0c;删除数组nums中重复出现的元素&#xff0c;使得nums中出现次数超过两次的元素只出现两次。返回删除后数组的新长度。 3 解法一&#xff1a;双指针 双指针法可以…...

探索HTMLx:强大的HTML工具

1. HTMLX htmx 是一个轻量级的 JavaScript 库&#xff0c;它允许你直接在 HTML 中使用现代浏览器的功能&#xff0c;而不需要编写 JavaScript 代码。通过 htmx&#xff0c;你可以使用 HTML 属性执行 AJAX 请求&#xff0c;使用 CSS 过渡动画&#xff0c;利用 WebSocket 和服务…...

NC65中间件能启动,前端客户端启动失败,加载异常,卡住(org.owasp.esapi)

控制台输出错误 ESAPI.properties could not be loaded by any means. Fail.SecurityConfiguration class(org.owasp.esapi.reference.DefaultSecurityConfiguration) CTOR threw exception.效果图&#xff1a; 解决方案 添加如下参数&#xff1a; -Dorg.owasp.esapi.resou…...

【大数据】YARN调度器及调度策略

YARN调度器 YARN负责作业资源调度&#xff0c;在集群中找到满足业务的资源&#xff0c;帮助作业启动任务&#xff0c;管理作业的生命周期。 ​ YARN技术架构 ​ 目前&#xff0c;Hadoop作业调度器主要有三种&#xff1a;先进先出调度器&#xff08;First In First Out&…...

如何快速入门Python指南

在数字化时代&#xff0c;掌握一门编程语言已成为众多行业和职业必备的技能之一。Python以其简洁易读的语法、丰富的库资源以及强大的跨领域应用能力&#xff0c;成为了初学者学习编程的理想选择。本文旨在为新手提供一套全面且深入的Python学习路径&#xff0c;并结合实践建议…...

vue3 页面长时间不使用,再次点击页面切换路由 操作无效报错

问题描述: 使用Vite打包构建的项目&#xff0c;重新部署到生产。在部署期间用户一直停留在当前项目页面&#xff08;长时间无操作 半个小时&#xff09;&#xff0c;部署完成后点击页面上的路由&#xff0c;报错&#xff01; 刷新后恢复正常。出现问题原因&#xff1a; 上线打…...

【算法练习】leetcode算法题合集之动态规划篇

普通动规系列 LeetCode343. 整数拆分 LeetCode343. 整数拆分 将10的结果存在索引为10的位置上&#xff0c;需要保证数组长度是n1&#xff0c;索引的最大值是n&#xff0c;索引是从0开始的。 n的拆分&#xff0c;可以拆分为i和n-i&#xff0c;当然i可以继续拆分。而且拆分为n-…...

青少年人工智能实验基地解决方案

1. 方案背景 1.1人工智能创新教育解决方案背景 人工智能已成为引领未来的新兴技术&#xff0c;中国将人工智能列为国家重点发展战略&#xff0c;对人工智能的发展做出了总体部署&#xff0c;全面加速人工智能在研发应用和人才培养的步伐。2021年1月教育部官网公布《关于政协十…...

10个让你的明星网红推广事半功倍的技巧-华媒舍

明星网红已成为市场推广和品牌宣传的重要方式。要在竞争激烈的市场中脱颖而出&#xff0c;并吸引更多的观众和粉丝&#xff0c;需要一些科学而有效的技巧。本文将向你介绍10个让你的明星网红推广事半功倍的技巧。 技巧一&#xff1a;建立个人品牌 成功的明星网红通常都有独特而…...

k8s集群异常恢复

前提、我自己的k8s采用的是单master节点两个从节点部署&#xff0c;我针对单master情况进行恢复说明 场景一&#xff1a;正常开关虚拟机&#xff0c;可直接重启kubelet进行恢复 1、1、一般重启后三个节点都需要检查&#xff0c;输入命令检查kubelet&#xff1a; systemctl s…...

NOC总线(2)

1. NoC的路由 在NoC交换信息时&#xff0c;需要确定从源节点到目标节点所经过的路径&#xff0c;这时就需要路由算法来确定该路径。路由算法分为静态路由算法和动态路由算法两种。 静态路由算法对于两节点之间的路径是固定的&#xff0c;结构简单&#xff0c;便于硬件实…...

2401llvm,clang的libtooling

LibTooling(库工具) LibTooling是个支持基于Clang编写独立工具的库. 在此,为LLVM安装Clang工具 介绍 用LibTooling构建的工具(如Clang插件)通过代码运行FrontendActions. 这里演示运行Clang的快速检查一堆代码语法的SyntaxOnlyAction的不同方法. 解析内存中的代码片 如果想…...

数据结构—基础知识(13):树的存储结构

数据结构—基础知识&#xff08;13&#xff09;&#xff1a;树的存储结构 双亲表示法 这种表示方法中&#xff0c;以一组连续的存储单元存储树的结点&#xff0c;每个结点除了数据域data外&#xff0c;还附设一个parent域用以指示其双亲结点的位置。 这种存储结构利用了每个结…...

【Python爬虫入门到精通】小白也能看懂的知识要点与学习路线

文章目录 1. 写在前面2. 爬虫行业情况3. 学习路线 【作者主页】&#xff1a;吴秋霖 【作者介绍】&#xff1a;Python领域优质创作者、阿里云博客专家、华为云享专家。长期致力于Python与爬虫领域研究与开发工作&#xff01; 【作者推荐】&#xff1a;对JS逆向感兴趣的朋友可以关…...

服务器数据恢复—EVA存储raid5硬盘离线的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌EVA某型号存储&#xff0c;底层是RAID5阵列&#xff0c;划分了若干lun。 服务器故障&分析&#xff1a; 该存储设备中raid5阵列有两块硬盘掉线&#xff0c;存储中的lun丢失。 将故障服务器存储中的所有磁盘编号后取出&#xff0c;硬件…...

MAMBA论文疑被拒收,计算机科学顶会评审遭质疑

2023 年底&#xff0c;卡内基梅隆和普林斯顿大学计算机系的两位年轻科学家&#xff08;Albert Gu, Tri Dao&#xff09;联合推出一种叫做“Mamba”的大语言模型&#xff08;LLM&#xff09;新构架。与Transformers等传统模型相比&#xff0c;Mamba能够更有效地处理长序列。它利…...

EHS管理系统为何需要物联网的加持?

EHS是Environment、Health、Safety的缩写&#xff0c;是从欧美企业引进的管理体系&#xff0c;在国外也被称为HSE。EHS是指健康、安全与环境一体化的管理。 而在国内&#xff0c;整个EHS市场一共被分成三类&#xff1b; 一类是EHS管培体系&#xff0c;由专门的EHS机构去为公司…...

记事本(父页面与iframe子页面的联通,vue3+ts展示fbx模型,与tga贴图)

vue3ts 展示fbx与tga贴图 npm i three --save <template><div ref"modelContainer"></div> </template><script setup lang"ts"> import { ref, onMounted } from vue; import * as THREE from three; import { FBXLoader…...

【好书推荐-第五期】《互联网大厂推荐算法实战》(异步图书出品)

&#x1f60e; 作者介绍&#xff1a;我是程序员洲洲&#xff0c;一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号&#xff1a;程序员洲洲。 &#x1f388; 本文专栏&#xff1a;本文…...

C++ Qt day2

自己封装一个矩形类(Rect)&#xff0c;拥有私有属性:宽度(width)、高度(height)&#xff0c; 定义公有成员函数: 初始化函数:void init(int w, int h) 更改宽度的函数:set_w(int w) 更改高度的函数:set_h(int h) 输出该矩形的周长和面积函数:void show() #include <io…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Mobile ALOHA全身模仿学习

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