0080. Remove Duplicates from Sorted Array II
============================================
题目信息
--------
:题号: 0080. 删除有序数组中的重复项 II
:难度: Medium
:主题: 有序数组、双指针、原地覆盖
:原题: `LeetCode 0080 `_
:重点: 从额外缓冲过滤,推导到重复段覆盖,再压缩为倒数第二项比较
题目重述
--------
给定一个按非递减顺序排列的整数数组 ``nums``,原地删除多余的重复项,使每个不同值最多出现两次。
返回处理后的有效长度 ``k``,并保证 ``nums`` 的前 ``k`` 个元素恰好是过滤后的结果。``k`` 之后的内容
不作要求。
算法必须直接修改输入数组,并使用 ``O(1)`` 额外空间。
约束为 ``1 <= nums.length <= 3 * 10^4``,``-10^4 <= nums[i] <= 10^4``。
自建示例
--------
.. code-block:: text
输入:nums = [0,0,0,1,1,1,1,2,3,3]
输出:k = 7
有效前缀:[0,0,1,1,2,3,3]
值 0 和 1 各保留前两个副本,值 2 保留一次,值 3 保留两次。
.. code-block:: text
输入:nums = [1,1,2,2,3]
输出:k = 5
有效前缀:[1,1,2,2,3]
所有重复次数都不超过两次,因此数组保持不变。
.. code-block:: text
输入:nums = [5,5,5,5]
输出:k = 2
有效前缀:[5,5]
同一数值连续出现四次,只保留最前面的两个副本。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int bufferedFilter(std::vector& nums) {
std::vector filtered;
filtered.reserve(nums.size());
for (int value : nums) {
if (filtered.size() < 2 ||
value != filtered[filtered.size() - 2]) {
filtered.push_back(value);
}
}
std::copy(filtered.begin(), filtered.end(), nums.begin());
return static_cast(filtered.size());
}
int segmentCounting(std::vector& nums) {
const int size = static_cast(nums.size());
int read = 0;
int write = 0;
while (read < size) {
const int value = nums[read];
int count = 0;
while (read < size && nums[read] == value) {
++read;
++count;
}
const int keep = std::min(count, 2);
for (int copy = 0; copy < keep; ++copy) {
nums[write++] = value;
}
}
return write;
}
int explicitRunCount(std::vector& nums) {
const int size = static_cast(nums.size());
int write = 0;
int runLength = 0;
for (int read = 0; read < size; ++read) {
if (read == 0 || nums[read] != nums[read - 1]) {
runLength = 1;
} else {
++runLength;
}
if (runLength <= 2) {
nums[write++] = nums[read];
}
}
return write;
}
int compareSecondLast(std::vector& nums) {
int write = 0;
for (int value : nums) {
if (write < 2 || value != nums[write - 2]) {
nums[write++] = value;
}
}
return write;
}
public:
int removeDuplicates(std::vector& nums) {
return compareSecondLast(nums);
}
};
题解
----
额外缓冲
~~~~~~~~
最直接的方法是把允许保留的元素依次写入新数组,再复制回 ``nums``。缓冲数组始终保持合法,因此当前值只需
与其中倒数第二项比较。这个方案容易验证,但额外空间为 ``O(n)``,未满足题目的原地要求。
有序数组中的相同值必然连续,所以不需要哈希表记录每个值的总次数。接下来只需把缓冲数组中的写入位置
移回原数组。
分段原地覆盖
~~~~~~~~~~~~
``segmentCounting`` 用 ``read`` 找出一个完整重复段,设其长度为 ``count``,然后把该值写入
``min(count, 2)`` 次。处理完一个重复段后,后续元素一定更大,旧值不会再次出现。
``write`` 始终指向有效前缀之后的第一个位置。每个重复段都恰好保留前两个副本,因此扫描完成时,
``nums[0:write]`` 已是所需结果。
显式重复次数
~~~~~~~~~~~~
无需等到重复段结束才写入。``explicitRunCount`` 从左到右维护当前值在所属重复段中的序号:
* 遇到新值时,``runLength`` 重置为 1;
* 遇到相同值时,``runLength`` 增加;
* 只有 ``runLength <= 2`` 时才写入。
这种写法把分段统计改成单层循环,但仍显式维护当前重复次数。
倒数第二项条件
~~~~~~~~~~~~~~
有效前缀本身按非递减顺序排列,并且每个值最多出现两次。准备写入 ``value`` 时分为两种情况:
* ``write < 2``:有效前缀不足两个元素,当前值不可能已经出现两次,可以直接保留;
* ``write >= 2``:比较 ``value`` 与 ``nums[write - 2]``。
若两者相等,由于有效前缀非递减,``nums[write - 1]`` 也等于 ``value``。有效前缀末尾已经有两个该值,
当前副本必须丢弃。
若两者不等,当前值在有效前缀末尾最多出现一次,写入后仍符合“最多两次”。这样便把显式计数压缩成一次
固定距离比较。
.. list-table::
:header-rows: 1
* - 当前读取值
- 写入前的有效前缀
- 判断
- 动作
* - 第一个 0
- ``[]``
- ``write < 2``
- 保留
* - 第二个 0
- ``[0]``
- ``write < 2``
- 保留
* - 第三个 0
- ``[0,0]``
- 等于倒数第二项
- 丢弃
* - 第一个 1
- ``[0,0]``
- 不等于倒数第二项
- 保留
* - 第三个 1
- ``[0,0,1,1]``
- 等于倒数第二项
- 丢弃
原地覆盖安全性
~~~~~~~~~~~~~~
扫描任意前缀时,写入的元素数量不会超过已读取元素数量,因此 ``write`` 总是不大于当前读取位置之后的
边界。写入只会发生在当前读取位置或其左侧,不会覆盖尚未读取的元素。
范围循环先把当前元素复制到局部变量 ``value``,再修改数组。即使写入位置恰好等于当前读取位置,本轮判断
使用的值也不会改变。
方法推广
~~~~~~~~
若规则改为“每个值最多保留 ``limit`` 次”,同一逻辑可写成:
.. code-block:: cpp
if (write < limit || value != nums[write - limit]) {
nums[write++] = value;
}
有序性保证:与距离 ``limit`` 的元素相同,就说明有效前缀末尾已经存在 ``limit`` 个当前值。
复杂度
~~~~~~
缓冲方法时间 ``O(n)``、额外空间 ``O(n)``。三种原地方法都只扫描数组一次,时间 ``O(n)``,额外空间
``O(1)``。返回值 ``write`` 即有效前缀长度,后续位置无需清理。