关于博主:
今天分享一道简单的关于“双指针”算法的题目。算是双指针中非常基础的题目,有兴趣可以借鉴一波~
目录
1.题目介绍
题目链接:LINK
本题要求是:对给定的有序数组nums
删除重复元素,使得每种元素仅在该数组中出现一次,并返回新的数组长度。请注意,上述操作必须在原数组中进行(即使用O(1)
空间复杂度去解决此问题)。
2.题解思路:双指针法
给定数组是有序的,任何相同的元素均相邻。 题目中介绍,这是一个非严格递增的数组,变相告诉我们该数组是有序的,因此我们可以推的该数组中所有重复元素按均相邻。
特殊情况,数组元素个数为0时返回0。 nums为0,则证明没有任何元素,可以直接返回0(这点题目中没有明确说明)。
一般情况,数组元素个数大于0。 一般情况下,数组中至少有一个元素,因此在删除重复元素之后也会至少剩下一个元素,因此我们可知nums[0]保持原样即可,不必修改,因为nums[0]是删除后一定存在的。因此我们从下标1处开始检查并删除元素。
快慢指针法:指定两个指针,一个fast指针(快指针)用于在数组前面遍历检查,另一个slow指针(满指针)用于把表示下一个不同元素填入指定下标位置。初始情况下,fast指向1(0处不用进行检查,因为必定不会被删除),slow指向0。
假设数组的总长度为n,按照快慢指针法快指针将依次遍历下标1-n-1处的数字,当检查到与slow位置的值不相同时,则++slow,把该不同的数据填入到slow位置下;如果fast指针遍历到的数字与slow相同,那么我们继续fast++;
返回值:遍历结束后,我们slow指向的位置及前面所有位置均是有效数字,我们返回slow + 1即可。
3.代码示例
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
// 双指针法解答
int slow = 0, fast = 1;//快慢指针
while(fast < nums.size())
{
if(nums[fast] != nums[slow])//如果快指针对应的值不等于慢指针
{
nums[++slow] = nums[fast];//满指针先++,再把不同的值拷贝给nums[slow]
}
fast++;//继续遍历下一个
}
return slow + 1;//返回慢指针+1
}
};
不知你是否还有更好的思路,欢迎评论分享~
EOF
标签:slow,删除,nums,元素,fast,数组,practise,指针 From: https://blog.csdn.net/2302_79031646/article/details/140965592