给你一个有序数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组,并在使用O(1)的额外空间的条件下完成。
示例:
输入:nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
输出:5, nums = [0, 1, 2, 3, 4]
说明:
为什么返回数值是整数,但输出的答案是数组呢?
因为数组是以引用的方式传递的,这就意味着在函数里修改数组对于调用者是可见的,所以返回时只需返回删除后数组的长度即可。
思路:
定义快慢指针,初始时慢指针指向数组第0个元素,快指针指向第1个元素。
比较快慢指针指向的元素,若相同则快指针往后移动一位,慢指针不动。
若快慢指针指向的元素不同,则慢指针先往后移动一位,然后将快指针指向的元素赋值给慢指针指向的位置,然后快指针再往后移动一位。
按照以上规则进行下去,知道快指针将数组遍历完毕,此时数组当中的布局如下:
这时从数组第0个元素开始到slow指针指向的元素,即为数组当中的非重复元素,而非重复元素个数即为slow+1。
代码如下:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) //空数组返回0
return 0;
size_t slow = 0, fast = 1; //定义快慢指针
for (fast = 1; fast < nums.size(); fast++) //快指针用于遍历数组
{
if (nums[fast] != nums[slow]) //快慢指针所指元素不同
{
slow++; //慢指针自增
nums[slow] = nums[fast]; //将快指针指向的元素赋值给慢指针
}
}
return slow + 1; //返回数组中非重复项的元素个数
}
};