删除排序数组中的重复项 (Remove Duplicates from Sorted Array)

Problem Statement

给一个非递减排序的整数数组 nums，原地删除重复项，使每个元素只出现一次。返回唯一元素的数量 k，且前 k 个位置放排序好的唯一值。

示例：

• [1,1,2] → k=2, nums=[1,2,_]
• [0,0,1,1,1,2,2,3,3,4] → k=5, nums=[0,1,2,3,4,_,_,_,_,_]

My Solution

原始思路（收到提示前）

创建一个整数向量存储唯一的数值。创建两个指针指向首节点。先判断首节点是不是空，是空就返还0和原数组……指针1移动到当前的next节点……当循环结束，重新将前k位的值替换成向量里面的数。

问题：这是数组不是链表，没有”节点”、”next”、”空节点”这些概念。而且创建额外向量违反了”原地”的要求。

提示后的新思路

关键洞察：数组已排序 → 重复值都挨在一起。只需遍历时跳过相邻重复即可。

代码（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <vector>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
      for (int i = 0; i < nums.size(); i++) {
        if (i + 1 < nums.size() && nums[i] == nums[i + 1]) {
          nums.erase(nums.begin() + i);
          i--;
        }
      }
      return nums.size();
    }
};

思路详解

遍历数组，发现相邻重复就 erase 当前元素，然后 i-- 回退重新检查同一位置。直观理解：每次看到两个相邻的相同数字，就删掉前面那个。

i-- 的正确性：i 变成 -1 是短暂的中间状态，循环体结束后 for 的 i++ 立刻把它拉回 0，不会造成数组越界访问。

调试过程

用 [0,0,1,1,1,2,2,3,3,4] 逐步跟踪：

1
2
3
4
5
6
7
8
9
10

i=0  [0,0,1,1,1,2,2,3,3,4]  删除索引0
i=0  [0,1,1,1,2,2,3,3,4]    跳过
i=1  [0,1,1,1,2,2,3,3,4]    删除索引1
i=1  [0,1,1,2,2,3,3,4]      删除索引1
i=1  [0,1,2,2,3,3,4]        跳过
i=2  [0,1,2,2,3,3,4]        删除索引2
i=2  [0,1,2,3,3,4]          跳过
i=3  [0,1,2,3,3,4]          删除索引3
i=3  [0,1,2,3,4]            跳过
i=4  [0,1,2,3,4]            结束

最终 [0,1,2,3,4]，k=5。

复杂度分析

• 时间：O(n²)，每次 erase 触发后续元素搬移，最坏情况（全重复）退化为平方级
• 空间：O(1)，原地操作

最优解（O(n) 双索引）

不使用 erase，而是用一个慢指针 k 记录写入位置，快指针 i 扫描全数组：

1
2
3
4
5
6
7
8
9

int removeDuplicates(vector<int>& nums) {
    int k = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (k == 0 || nums[i] != nums[k - 1]) {
            nums[k++] = nums[i];
        }
    }
    return k;
}

k 既是唯一元素个数，也是下一个写入位置。不需要删除任何元素，直接覆盖。

审查发现

同类题目

• #27 Remove Element — 同样双指针覆盖思路，去掉指定值
• #80 Remove Duplicates from Sorted Array II — 升级版，允许每个元素出现两次