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

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

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

思路

数组遍历第一次，找出应当返回的数组长度。

数组遍历第二次，用两个指针，分别指向ref数组（没有改变的nums数组）和nums数组的当前值。

ref数组判断，超过两个相同的数，自动往下寻找不同的数。将ref数组的当前值赋给nums数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0; 
        int[] ref = new int[nums.length];
        int length = 0;
        int count = 0;
        
        for (int i = 0; i < nums.length - 1; i++){
            ref[i] = nums[i];
            if(nums[i] == nums[i+1]){
                count++;
            }
            else{
                if(count > 0) length += 2;
                else length += 1;
                count = 0;
            }
        }
        if(count > 0) length += 2;
        else length += 1;
        ref[nums.length-1] = nums[nums.length-1];
        
        int cnt = 0;
        if(length != nums.length){
            int j = 0;
            for(int i = 0; i < length; i++){
                if(j < nums.length -1){
                    if(ref[j] != ref[j+1]){
                        nums[i] = ref[j];
                        j++;
                        cnt = 0;
                    }
                    else{
                        cnt++;
                        if(cnt > 1){
                            while(j < nums.length -1 && ref[j] == ref[j+1]) j++;
                            cnt = 0;
                        }
                        nums[i] = ref[j];
                        j++;
                    }
                }
                else nums[i] = nums[j];
            }
        }
        return length;
    }
}

参考资料：

https://discuss.leetcode.com/topic/46519/short-and-simple-java-solution-easy-to-understand
https://www.xiadong.info/2016/08/13/leetcode-80-remove-duplicates-from-sorted-array-ii/