1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int removeDuplicates(int[] nums) {
        int nextPlace = 1, ptr = 1, count = 1;
        while (ptr < nums.length) {
            if (nums[ptr] != nums[ptr - 1]) {
                count = 1;
                nums[nextPlace] = nums[ptr];
                nextPlace += 1;
            } else if (nums[ptr] == nums[ptr - 1] && count < 2) {
                nums[nextPlace] = nums[ptr];
                count += 1;
                nextPlace += 1;
            }
            ptr += 1;
        }
        return nextPlace;
    }
}

还是两个指针的原则. 一个指针表示下一个valid的num应该放在的位置, 另一个指针就是去遍历数字. 我们需要记录的是连续出现的数字的count. 如果出现count == 2且又遇到了重复的数字, 那么此时这个数字就不能放在valid的位置了, 我们只能无情地让ptr增加. 如果出现此时数字和前一个数字一样当时count是1或者当前的数字和前一个数字不同, 那么此时我们就可以让valide的位置装这个数字, 然后同时更新ptr和nextPlace. 需要注意的是如果当前数字和前一个数字不同, 我们需要reset count到1, 这个1表示的就是当前的数字连续出现频率了.

时间复杂度: O(n)
空间复杂度: O(1)