描述 Description

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,

Given input array nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

[Remove Duplicates from Sorted Array]

类似思路[Remove Element]

[Move Zeroes]和"Remove Element" 思路一模一样，只是最后要把后半截设置为0。

分析 Analysis

"删除多余元素"其实不是真的删除，因为题目要求不能用额外的空间，所以最好的思路是替换，只要把后面的元素放到前面来就行了。

用2个指针:

• 1个指针i从1移动到length
• 1个指针newlen记录不重复的个数，只有出现不重复的时候它才能+1

时间复杂度O(n)，空间复杂度O(1)。

代码 Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;

        int index = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[index - 1])
                nums[index++] = nums[i];
        }
        return index;
    }
};

int count = 0;
for(int i = 1; i < n; i++){
    if(A[i] == A[i-1]) count++;
    else A[i-count] = A[i];
}
return n-count;