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

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

思路：双指针法。只不过这次是前面隔一个元素比较。

public class Solution {

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

    public int removeDuplicates2(int[] A) {
        if (A.length <= 2)
            return A.length;

        int prev = 1; // point to previous
        int curr = 2; // point to current

        while (curr < A.length) {
            if (A[curr] == A[prev] && A[curr] == A[prev - 1]) {
                curr++;
            } else {
                prev++;
                A[prev] = A[curr];
                curr++;
            }
        }

        return prev + 1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().removeDuplicates(new int[] { 1, 1, 1, 2 }));
        System.out.println(new Solution().removeDuplicates(new int[] { 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5 }));
        System.out.println(new Solution().removeDuplicates(new int[] {}));
        System.out.println(new Solution().removeDuplicates(new int[] { 1 }));
        System.out.println(new Solution().removeDuplicates(new int[] { 1, 1 }));
    }

}

View Code

第二遍记录：

　　总体思想还是双指针法，cur负责遍历，pre负责赋值，注意寻找移动的规则。

public int removeDuplicates(int[] A) {
        if (A.length <= 2)
            return A.length;
 
        int prev = 1; 
        int curr = 2; 
 
        while (curr < A.length) {
            if (A[curr] == A[prev] && A[curr] == A[prev - 1]) {
                curr++;
            } else {
                prev++;
                A[prev] = A[curr];
                curr++;
            }
        }
 
        return prev + 1;
    }

好理解的解法2：

每次统计每个数字的个数count，i表示当前可以被拷贝的位置。

public class Solution {
    public int removeDuplicates(int[] A) {
        int i = 0;
        int j = 0;

        while (j < A.length) {
            int count = 1;

            while (j + 1 < A.length && A[j + 1] == A[j]) {
                ++count;
                ++j;
            }

            A[i++] = A[j];

            if (count > 1) {
                A[i++] = A[j];
            }

            ++j;
        }

        return i;
    }
}

参考：

http://www.programcreek.com/2013/01/leetcode-remove-duplicates-from-sorted-array-ii-java/

http://zhangxc.com/2013/11/leetcode-remove-duplicates-from-sorted-array-2