给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
思路我一开始的思路是:先选定第0个元素,把后面的每个元素一次与其比较,如果重复,则把后面的所有元素一次往前移动一位。这样遍历一遍后,在选定第二个元素,重复上述操作。这样写起来十分复杂,且时间复杂度为O(n^2)。
答案的做法是双指针。分别定义slow=0,fast=1,当nums[slow]与nums[fast]相等时,fast自增1指向下一元素,再次比较。如果不相等,则赋值到nums[slow+1],slow再自增1。 如图所示。
class Solution {
public:
int removeDuplicates(vector& nums) {
int n=nums.size();
if(n==0) return 0;
int fast=1,slow=0;
while(fast 


