LeetCode 80 Remove Duplicates from Sorted Array II

描述

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

Example 1:

1
2
3
4
5
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。

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

解题

1
2
3
4
5
6
7
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

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

本文标题:LeetCode 80 Remove Duplicates from Sorted Array II

文章作者:Pylon, Syncher

发布时间:2020年03月10日 - 21:03

最后更新:2020年05月19日 - 22:05

原始链接:https://0x400.com/2020-03-10-lc-80-remove-duplicates-from-sorted-array-ii.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。