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

 

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

 

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 }));    }}

 

第二遍记录：

　　总体思想还是双指针法，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;    }}

　　

 

 

参考：