LeetCode 80 Remove Duplicates from Sorted Array II

描述

给定一个数组，删除部分元素使得所有元素最多重复两次。

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.

分析

基于 xx 题的思路，两个指针l, r, r 指向当前遍历元素 ，l 指向当前有效元素的末尾。思考：

- l 和 r 起始位置应该在哪里? ~
- l 和 r 的移动规则？

首先 l 和 r 起始位置都在第 3 个元素，即 r = l = 3，因为前两个元素一定符合题意，因为最多重两次

判断 r 指向元素是否重复两次以上，如果否同时向后移动 l 和 r。

如果是则只移动 r 到下一个不与当前元素重复的元素，然后将 r 指向的元素复制到 l 指向的位置，再移动 r。

以上是我的思考，但是逻辑非常复杂，程序实现很困难。所以我放弃了这个思路，然后查阅资料发现此题和第一题近乎一模一样，只不过更新条件变更一下，看如下代码。

解题

def solve(A):
    new_tail = 2
 	for i in range(2, len(A)):
        if A[i] != A[new_tail - 2]:
            A[new_tail] = A[i]
            new_tail += 1
    return new_tail

简直太简单了，发现还是自己太菜了，加强学习吧。