Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。
🌈个人主页:主页链接
🌈算法专栏:专栏链接
现已更新完KMP算法,之后我会继续往里填充内容哒。
🌈LeetCode专栏:专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出
🌈代码仓库:Gitee链接
🌈点击关注=收获更多优质内容🌈
本题是LeetBook基础算法 中的一道简单题,主要思想为:利用双指针去消除重复的数字。
题目:
给你一个 升序排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
程序语言解释:
有一个数组,里面有一些排序完(从小到大)的数字,在不另外使用空间的情况下(不创建数组等容器),删除当中重复的数字,返回整理完的数组长度。
题解:
主要思想:双指针
假设有这样一组数据
i | j |
||||||||
0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 |
3 | 4 |
初始化两个指针i=0,j=1。当nums[i]!=nums[j]的时候,i指针向前移动一格,此时nums[i]=nums[j],是下图这种情况。
i j |
|||||||||
0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 |
3 | 4 |
j指针向后移动,当出现nums[i]!=nums[j]时
i |
j | ||||||||
0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 |
3 | 4 |
执行i++,然后令nums[i]=nums[j],
i | j | ||||||||
0 | 1 | 2 | 1 | 2 | 2 | 2 | 3 |
3 | 4 |
如此循环往复,就得到了这样的一个数组
i | j | ||||||||
0 | 1 | 2 | 3 | 4 | 2 | 2 | 3 |
3 | 4 |
当j=len时表示遍历结束,此时i位于新容器的末位,在执行++i,此时i就为新容器的长度。
#include<iostream> #include<vector> using namespace std; //[0,1,2,3,4,2,2,3,3,4] class Solution { public: int removeDuplicates(vector<int>& nums) { int i=0,j=1,len=nums.size(); for(;j<len;j++) { if(nums[i]!=nums[j]) nums[++i]=nums[j]; } return ++i; } };
代码思路:
创建两个指针 i,j。以及一个变量len存储nums的长度。
进行一个循环,条件为(j<len),若当前i指向的元素与j指向的元素不同,则让i向前移动一个位置后=j指向的值。
返回值为++i的大小,因为假设数组大小为4,那么他是0 1 2 3的下标,所以要返回++i;
完结撒花:
🌈本篇博客的内容【LeetCode每日一题26. 删除有序数组中的重复项】已经结束。
🌈本篇代码链接:Gitee
🌈LeetCode:删除有序数组中的重复项
🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。
🌈诸君,山顶见!