当前位置:网站首页>LeetCode·27.移除元素·双指针
LeetCode·27.移除元素·双指针
2022-08-10 18:29:00 【小迅想变强】
链接:https://leetcode.cn/problems/remove-element/solution/by-xun-ge-v-05jn/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
解题思路
双指针
删除数组中存在的元素,题目给定数组为指针,说明nums指向原始数组的地址,我们修改nums相当于修改了nums指向的地址,所以返回修改之后nums长度即可
对于本题我们定义两个指针,一个指向数组,遍历数组所有元素,当数组元素等于val时,另外一个指针将当前位置之后的所有元素都向前移位,相当于删除操作
双指针优化
在上述解法中,我们需要遍历还需要搬运元素,时间复杂度为O(n^2),我们可以将遍历和搬运简化到一个循环中,定义双指针,当数组元素相同时,慢指针留着当前位置,快指针进行前进,直到不相等时,将快指针指向位置搬运到当前慢指针位置
具体看代码,注释超级详细
代码
双指针
int removeElement(int* nums, int numsSize, int val){
for(int i = 0; i < numsSize; i++)//遍历数组
{
if(nums[i] == val)//相同时,将后面元素搬上来
{
for(int j = i+1; j < numsSize; j++)//搬元素
{
nums[j-1] = nums[j];
}
i--;//当前位置已经被新元素代替了,需要重新访问,是否还是相同元素比如3,3,2,2要删除3,
numsSize--;//长度-1
}
}
return numsSize;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/remove-element/solution/by-xun-ge-v-05jn/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
双指针优化
int removeElement(int* nums, int numsSize, int val){
int i, j;//定义快慢指针
for(i = 0, j = 0; i < numsSize; i++)//遍历整个数组
{
if(nums[i] == val)//快指针进行走
{
continue;
}
nums[j++] = nums[i];//慢指针搬元素
}
return j;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/remove-element/solution/by-xun-ge-v-05jn/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
边栏推荐
猜你喜欢
随机推荐
【测试】黑盒测试用例设计方法
Unity_Stack<T>()的应用(多个次级界面后的返回逻辑)
Consul Introduction and Installation
003-序列图(一)
工业基础类—利用xBIM提取IFC几何数据
【数据存储精讲】整型和浮点型有什么区别?为什么会精度丢失?
三坐标雷达显示软件 SPx Viewer-3D
瑞吉外卖学习笔记4
测试接口出现“data“: “Full authentication is required to access this resource“凭证已过期
6-12 二叉搜索树的操作集(30分)
2022-08-09 Study Notes day32-IO Stream
阿里云贾朝辉:云 XR 平台支持彼真科技呈现国风科幻虚拟演唱会
「POJ 3666」Making the Grade 题解(两种做法)
【HMS core】【FAQ】Account Kit、push Kit典型问题合集1
21天打卡挑战学习MySQL——《MySQL表管理》第二周 第五篇
MySQL 原理与优化:Update 优化
罗克韦尔Rockwell Automation EDI 项目
多线程与高并发(五)—— 源码解析 ReentrantLock
入门:人脸专集2 | 人脸关键点检测汇总(文末有相关文章链接)
高手问答第 290 期 —— SaaS产品经理从菜鸟到专家