当前位置: 首页 > 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…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学

一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件&#xff0c;其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时&#xff0c;价带电子受激发跃迁至导带&#xff0c;形成电子-空穴对&#xff0c;导致材料电导率显著提升。…...

OPENCV图形计算面积、弧长API讲解(1)

一.OPENCV图形面积、弧长计算的API介绍 之前我们已经把图形轮廓的检测、画框等功能讲解了一遍。那今天我们主要结合轮廓检测的API去计算图形的面积&#xff0c;这些面积可以是矩形、圆形等等。图形面积计算和弧长计算常用于车辆识别、桥梁识别等重要功能&#xff0c;常用的API…...