80. Remove Duplicates from Sorted Array II

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

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given 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 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Thoughts

对给定数组压缩：重复元素至多出现两次。前后双指针，后指针每次前进一格并比较当前字符和后面是否一致（或到了最后一个字符），一致时跳过；否则在前指针位置开始替换，如果num[i] 和num[i-1]也一样说明出现了至少两次，则替换两次。

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 0
        for i, num in enumerate(nums):
            if i == len(nums) - 1 or num != nums[i + 1]:
                if i > 0 and num == nums[i - 1]:
                    nums[j] = nums[i]
                    j += 1
                nums[j] = nums[i]
                j += 1
        return j

/*
 * @lc app=leetcode id=80 lang=cpp
 *
 * [80] Remove Duplicates from Sorted Array II
 */
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 2) return nums.size();
        int pos = 2;
        for (int i = pos; i < nums.size(); ++i) {
            if (nums[pos - 1] == nums[pos - 2] && nums[pos - 1] == nums[i]) continue;
            nums[pos++] = nums[i];
        }
        return pos;
    }
};

Analysis

Errors:

1. 先没想到问题本质, 没有数数目, 只想能直接替换, 绕在了nums[i], nums[i -2]和pos在i -2和i之间时的关系上了.

2. 没有想到可以让pos和i同时往前走, 这样更清晰. 因为如[1,1]时如果不是同时走的而是只在else里更新nums[pos]则会少个1.

3. pos和要返回总数目的关系

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