leetcode打卡-0080删除有序数组中的重复项II
题目描述
给你一个有序数组nums,请你原地删除重复出现的元素,使每个元素最多出现两次,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii
解题思路
1. 通用套路
这题和leetcode第26题-删除数组中重复数,几乎一样的思路,26题是只保留1个,此题是保留2个,已经在这里记录过题解。
- 由于是保留2个相同数字,对于前2个数字,我们可以直接保留。
- 对于后面的任意数字,能够保留的前提是:与当前写入的位置前面的第2个元素进行比较,不相同则保留。
将问题衍生至保留k个数字,则可以扩展为:
在有序数组的前k个元素里,每种数字都会符合不超过k个的条件;反向思考,一个数字与写入位置的第前k个元素对比,如果相同,证明写入位置之前已经写满了k个当前元素,那么写入位置就需要寻找一个新元素写入了,如果不同,就把当前元素复制过去补位。
所以,通用的Python实现代码如下:
1 | def process(nums, k): |
- 时间复杂度O(n)
- 空间复杂度O(1)
那么这题的题解就可以写成:
1 | # Python3实现 |
练习一下Rust
1 | impl Solution { |
总结
参考之前的题解,注意总结顺序遍历中“保留逻辑”的套路。