remove_duplicates_from_sorted_array.md

Remove Duplicates from Sorted Array

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 A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

这道题目与前一题Remove Element比较类似。但是在一个排序好的数组里面删除重复的元素。

首先我们需要知道，对于一个排好序的数组来说，A[N + 1] >= A[N]，我们仍然使用两个游标i和j来处理，假设现在i = j + 1，如果A[i] == A[j]，那么我们递增i，直到A[i] != A[j]，这时候我们再设置A[j + 1] = A[i]，同时递增i和j，重复上述过程直到遍历结束。

代码如下：

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n == 0) {
            return 0;
        }

        int j = 0;
        for(int i = 1; i < n; i++) {
            if(A[j] != A[i]) {
                A[++j] = A[i];
            }
        }
        return j + 1;
    }
};

譬如一个数组为1，1，2，3，首先i = 1，j = 0，这时候A[i] = A[j]，于是递增i，碰到2，不等于1，此时设置A[j + 1] = A[i]，也就是A[1] = A[2]，递增i和j为3和1，这时候A[3] != A[1]，设置A[j + 1] = A[i]，也就是A[2] = A[3]，再次递增，遍历结束。这时候新的数组长度就为2 + 1，也就是3。

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?

For example, Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

紧接着上一题，同样是移除重复的元素，但是可以允许最多两次重复元素存在。

仍然是第一题的思路，但是我们需要用一个计数器来记录重复的次数，如果重复次数大于等于2，我们会按照第一题的方式处理，如果不是重复元素了，我们将计数器清零。

代码如下：

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n == 0) {
            return 0;
        }

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