Leetcode26——引出c++ vector中erase()的内部原理

erase是对数组中某个元素进行删除的操作,实际的时间复杂度为O(n)

预备知识

数组在内存中是连续存储的,删除某个位置的时候不能直接删除,只能用后序的元素覆盖
在这里插入图片描述
以nums数组为例,target为需要删除的目标数据

方法:

①暴力删除法:

每次遇到一个目标删除数据,后续的元素都要往前移动替代它
时间复杂度为O(n^2)
在这里插入图片描述

int del(vector<int> nums, int target){
	int size = nums.size();
	for(int i = 0; i < nums.size(); i++){
		//如果i所指元素为目标元素,则用后序元素替代
		if(nums[i] == target){
			for(int j = i+1; j < nums.size(); j++)
				nums[j-1] = nums[j];
			i--;//因为nums[i]已经被后序元素替代了,需要重新检查,所以回退一个
			size--;//数组的长度缩小一个
		}
	}
	return size;//返回数组的最终大小
}

②双指针法

时间复杂度:O(n)
思路
初始化两个指针
①慢指针逐个前进,表示下一个可使用的位置
②快指针指向第一个不等于目标值的位置
不断用快指针位置的值覆盖慢指针位置的值
相当于将非目标值的元素都堆到最前面
最后,fast走完整个数组,slow指的位置就是非目标值元素的个数,即size
在这里插入图片描述
代码

int del(vector<int> nums, int target){
	int slowindex = 0;
	for(int fastindex = 0; fastindex < nums.size(); fastindex++){
		//如果快指针非目标删除元素,放到前面
		if(nums[fastindex] != target){
			nums[slowindex++] = nums[fastindex];
	}
	return slowindex;//返回数组的最终大小
}

【注】
在不要求保证原数组顺序的情况下,也可以两指针相向而行,用后面的元素替代前面的

T26-题目

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

示例 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 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列

T26-解答

class Solution {
public:
	//从slow开始删除target元素
    int delFiction(vector<int>& nums, int target, int size, int slow, int fast){
    	//这里的size得是删除过后的size
        for(; fast < size; fast++){
            if(nums[fast] != target){
                nums[slow++] = nums[fast]; 
            }
                
        }
        return slow;
    }

    int removeDuplicates(vector<int>& nums) {
        int size = nums.size();
        for(int i = 0; i< size; i++){
        	//如果当前元素和下一个元素一样,就认为重复了
            if(i < size - 1 && nums[i] == nums[i+ 1] ){
                size = delFiction(nums, nums[i], size, i+1, i+1);
                i--;
            }
        }
        return size;
    }
};

相似题目:

T283

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/319246.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Windows无法登录管理路由器故障排查

问题描述 家里的路由器使用拨号上网&#xff0c;路由器DHCP分发IP的范围是192.168.1.0/24。默认使用192.168.1.1管理路由器。然后拨号上网成功后&#xff0c;修改了私网IP的分发范围&#xff1a;192.168.5.1-192.168.5.10。为了防止有人蹭网&#xff0c;只分配的10个IP地址。修…

Android Studio由于开启代理无法下载依赖,一直在Build model

一、问题描述 正常打开AS项目&#xff0c;一直显示Build model就是不下载依赖 二、问题解决 1、首先选择No Proxy&#xff0c;可以看到这位同学之前是使用的代理。 2、打开下面文件&#xff0c;然后删除某尾的4行。 3、面对提示框&#xff0c;直接点击OK。 4、然后停…

Trans论文复现:基于数据驱动的新能源充电站两阶段规划方法程序代码!

适用平台&#xff1a;MatlabYalmipCplex/Gurobi&#xff1b; 文章提出了一种电动汽车充电站的两阶段规划方法&#xff0c;第一阶段通过蒙特卡洛法模拟充电车辆需求和电池充放电数据来确定充电站位置&#xff1b;第二阶段通过数据驱动的分布鲁棒优化方法优化充电站的新能源和电池…

用Lisp的方言HY跑飞桨训练和推理

用Lisp的方言HY跑飞桨训练和推理 整个项目可以在AIStudio一键跑通&#xff1a;用Lisp的方言HY跑飞桨训练和推理 - 飞桨AI Studio星河社区 初见Lisp 估计很多人都看过《黑客与画家》这本书&#xff0c;百度百科中的条目&#xff1a;《黑客与画家&#xff1a;硅谷创业之父paul…

NUS CS1101S:SICP JavaScript 描述:一、使用函数构建抽象

原文&#xff1a;1 Building Abstractions with Functions 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 心灵的行为&#xff0c;其中它对简单的想法施加其力量&#xff0c;主要有以下三种&#xff1a;1.将几个简单的想法组合成一个复合的想法&#xff0c;从而形成所…

阿里状态机引擎实现

状态机的技术选型看这篇就够了&#xff0c;最后一个直叫好&#xff01; - 掘金 实现一个状态机引擎&#xff0c;教你看清DSL的本质_cola状态机-CSDN博客 一、引入jar包 <!--阿里状态机jar--> <dependency><groupId>com.alibaba.cola</groupId><a…

Python | 三、函数

函数的形参和实参&#xff08;对应卡码网11题句子缩写&#xff09; 除非实参是可变对象&#xff0c;如列表、字典和集合&#xff0c;则此时形参会复制实参的地址&#xff0c;即此时二者指向同一个地址&#xff0c;因此在函数内对形参的操作会影响到实参除这种情况外&#xff0…

Spring自带分布式锁你用过吗?

环境&#xff1a;SpringBoot2.7.12 本篇文章将会为大家介绍有关spring integration提供的分布式锁功能。 1. 简介 Spring Integration 是一个框架&#xff0c;用于构建事件驱动的应用程序。在 Spring Integration 中&#xff0c;LockRegistry 是一个接口&#xff0c;用于管理…

推荐两款好用的卫星地图。

问题描述&#xff1a;推荐两款好用的卫星地图。 问题解决&#xff1a;谷歌地球、高德卫星地图。个人感觉谷歌地球好用一些。

ST工具Flash Loader烧写STM32

简介 使用ST公司自家的Flash Loader烧写程序&#xff0c; 如下图, F103直接接USART1到PC端就好, 使用普通的USB转TTL线&#xff0c; 就是你之前使用串口打印的方式连接到电脑就好。 软件下载 ST Flash Loader 我放到CSDN里面了Flash_Loader_demo_v2.8.0 开发板设置 Boot0-&g…

序章 熟悉战场篇—了解vue的基本操作

了解vue 的基本目录&#xff1a; dist 是打包后存放的目录(后续可以改)node_modules 是依赖包public 是静态index页面src 是存放文件的目录assets 是存放静态资源的目录components 是存放组件的目录views 是存放页面文件的目录&#xff08;没有views 自己新建一个&#xff09;A…

动态规划篇-03:打家劫舍

198、打家劫舍 状态转移方程 base case 边界问题就是&#xff1a;走到最后一间房子门口也没抢&#xff0c;那么最终抢到的金额为0 明确状态 “原问题和子问题中会变化的变量” 抢到的金额数就是状态&#xff0c;因为随着在每一件房子门口做选择&#xff0c;抢到的金额数会随…

Unity中的异步编程【7】——在一个异步方法里播放了animation动画,取消任务时,如何停止动画播放

用一个异步方法来播放一个动画&#xff0c;正常情况是&#xff1a;动画播放结束时&#xff0c;异步方法宣告结束。那如果我提前取消这个异步任务&#xff0c;那在这个异步方法里面&#xff0c;我要怎么停止播放呢&#xff1f;&#xff01; 一、播放animation动画的异步实现 1…

RIP【新华三与华为区别】

【介绍】 rip分为rip 1 与 rip 2 &#xff0c;rip 2 是对 rip 1 的一种升级&#xff0c;rip 2 可以进行认证等功能 【命令】 新华三&#xff1a; [HC3-R1] rip #启用rip [HC3-R1-rip] version 2 #告知rip 版本号 [HC3-R1-rip] network 192.168.1.0 #宣告其网段 [HC3-R1-rip] …

【AIGC】电影风格的一组绝美高清图提示词解析

实际示例 女人主角&#xff0c;以时尚电影风格为灵感&#xff0c;追求照片般的逼真度&#xff0c;运用伦勃朗式光线&#xff0c;创造奇幻且细节丰富的场景&#xff0c;充满象征意义&#xff0c;使用3D渲染技术达到8K超高清晰度。 分类相关信息主角女人风格时尚电影风格逼真度…

银行储蓄系统的顶层数据流图及细化数据流图

绘制出银行储蓄系统的顶层数据流图及细化数据流图&#xff1b; 银行储蓄系统存、取款流程如下&#xff1a; 1&#xff09;业务员事先录入利率信息&#xff1b; 2&#xff09;如果是存款&#xff0c;储户填写存款单&#xff0c;业务员将存款单键入系统&#xff0c;系统更新储户存…

力扣周赛第二题,下午更新后两道

本题中其实看着条件很多&#xff0c;但是仔细读一下会发现&#xff0c;前四个条件都是固定条件。然后我们再看题。 我们的暴力做法是遍历a数组的字符串a的下标起始下标&#xff0c;然后遍历b数组的字符串b的下标起始下标&#xff0c;进行判断&#xff0c;但是这样会超时&#x…

[软件工具]通用OCR识别文字识别中文识别服务程序可局域网访问

【软件界面】 【算法介绍】 采用业界最先进算法之一paddlocr&#xff0c;PaddleOCR&#xff0c;全称PaddlePaddle OCR&#xff0c;是一种基于深度学习的光学字符识别&#xff08;OCR&#xff09;技术。相较于传统的OCR技术&#xff0c;PaddleOCR具有许多优点。 首先&#xff0…

如何创建一个pytorch的训练数据加载器(train_loader)用于批量加载训练数据

Talk is cheap,show me the code! 哈哈&#xff0c;先上几段常用的代码&#xff0c;以语义分割的DRIVE数据集加载为例&#xff1a; DRIVE数据集的目录结构如下&#xff0c;下载链接DRIVE,如果官网下不了&#xff0c;到Kaggle官网可以下到&#xff1a; 1. 定义DriveDataset类&…

Kibana:使用反向地理编码绘制自定义区域地图

Elastic 地图&#xff08;Maps&#xff09;附带预定义区域&#xff0c;可让你通过指标快速可视化区域。 地图还提供了绘制你自己的区域地图的功能。 你可以使用任何您想要的区域数据&#xff0c;只要你的源数据包含相应区域的标识符即可。 但是&#xff0c;当源数据不包含区域…