LeetCode: Remove Duplicates from Sorted Array I & II

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].

---

 

还是双指针的思想，i表示的是要处理的元素，start表示的是应该填充的位置。

如果A[i] != A[start-1]，说明这个元素不是重复的元素，或者是第一次出现，所以应该填充到start的位置上，start移到下一个应该填充的位置。因为start之前是处理过的元素，所以与start-1相等一定是重复元素。

而且start从1开始也是说明第一个要填充的位置是A[1]。因为A[0]不可能是重复的。

public int removeDuplicates(int[] A) {
        int start = 1;
        if (A.length == 0) return 0;
        for (int i = 0; i<A.length; i++) {
            if( i>0 && A[i] != A[start-1]) {
                A[start++] = A[i];
            }
        }
        return start;
    }

 

---

 

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].

现在可以一个元素重复两次。和上面方法一样。但是我想了好长时间，最后看的别人的代码理解的。

start之前都是处理好的元素，如果一个元素与start-2相等，就说明这个元素至少是第三次出现，应该删除。上面一个可以将A[start-1]换成A[i-1]。因为与A[i-1]比较也可以判断这是不是一个重复元素。但是这里不能把A[start-2]换成A[i-2],因为A[i-2]的元素可能已经被改变，无法判断A[i]是不是重复元素。

扩展：由此就可以得到任意重复元素的做法。比如可以重复3次，那么就把函数中的2都换成3就行了。

public int removeDuplicates(int[] A) {
        if (A.length <= 2) return A.length;
        int start = 2;
        for (int i=2; i<A.length; i++) {
            if (A[i] != A[start-2]) {
                A[start++] = A[i];
            }
        }
        return start; 
    }