【C++】原地删除有序数组重复元素：两种解法的深度剖析

一、问题描述

题目要求

给定一个非严格递增排列的整数数组nums，需要原地删除重复出现的元素，使得每个元素只出现一次，并返回删除后数组的新长度。

具体要求

1. 元素的相对顺序必须保持一致

2. 返回唯一元素的数量 k

3. 数组的前 k 个元素应包含去重后的唯一数字

4. 下标 k-1 之后的元素可以忽略

示例

cpp

输入: nums = [1,1,2] 输出: 2, nums = [1,2,_] 解释: 函数应返回长度 2，原数组的前两个元素修改为 [1,2] 输入: nums = [0,0,1,1,1,2,2,3,3,4] 输出: 5, nums = [0,1,2,3,4,_,_,_,_,_]

二、解法一：迭代器与 erase 操作

代码实现

cpp

class Solution { public: int removeDuplicates(vector<int>& nums) { vector<int>:: iterator it = nums.begin(); ++it; // 从第二个元素开始 while(it != nums.end()) { if((*it) == *(it - 1)) // 当前元素与前一个元素相同 { it = nums.erase(it); // 删除当前元素 } else { ++it; // 移动到下一个元素 } } return nums.size(); } };

算法分析

1. 核心思路

• 使用迭代器遍历数组

• 比较当前元素与前一个元素

• 如果相同，使用erase删除当前元素

• 如果不同，移动到下一个元素

2. 关键细节

cpp

// 为什么从第二个元素开始？ // 第一个元素无需与前面的元素比较（没有前面的元素） ++it; // it 初始指向 nums.begin()，++it 后指向第二个元素 // 为什么比较 it 和 it-1？ // 因为数组已排序，重复元素相邻 if((*it) == *(it - 1)) // erase 的返回值是什么？ // erase 返回指向被删除元素之后元素的迭代器 it = nums.erase(it); // 删除后 it 自动指向下一个有效元素

3. 执行流程示例

text

初始: [1,1,2,2,3] ↑ it (指向第二个1) 步骤1: it指向1，与前一个1相同 → 删除 → [1,2,2,3] 步骤2: it指向2，与前一个1不同 → ++it → [1,2,2,3] 步骤3: it指向第二个2，与前一个2相同 → 删除 → [1,2,3] 步骤4: it指向3，与前一个2不同 → ++it → 到达end 结果: [1,2,3]，长度3

4. 时间复杂度分析

• 最坏情况: O(n²)

  • erase操作需要移动后续所有元素

  • 假设删除 n 个元素，每次平均移动 n/2 个元素

• 平均情况: O(n²)

• 空间复杂度: O(1)（原地操作）

5. 优缺点

优点:

• 代码直观，易于理解

• 真正修改了数组大小

• 不需要额外空间

缺点:

• 效率低，频繁移动元素

• 不适合大数据量

• 不是最优解

三、解法二：双指针法（推荐）

代码实现

cpp

class Solution { public: int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; int slow = 0; // 慢指针，指向已去重部分的末尾 for (int fast = 1; fast < nums.size(); ++fast) { // 当快指针指向的元素与慢指针不同时 if (nums[fast] != nums[slow]) { ++slow; // 慢指针前进 nums[slow] = nums[fast]; // 复制不重复的元素 } // 如果相同，快指针继续前进，慢指针不动 } return slow + 1; // 返回新长度 } };

算法分析

1. 核心思想

• 使用两个指针：快指针fast和慢指针slow

• slow指向已去重部分的最后一个元素

• fast遍历整个数组

• 当发现新元素时，将其复制到slow+1的位置

2. 可视化演示

text

初始状态: [0,0,1,1,1,2,2,3,3,4] s f 步骤1: f=1, nums[f]=0, nums[s]=0 → 相同 → f++ [0,0,1,1,1,2,2,3,3,4] s f 步骤2: f=2, nums[f]=1, nums[s]=0 → 不同 → s++, nums[s]=nums[f] [0,1,1,1,1,2,2,3,3,4] s f 步骤3: f=3, nums[f]=1, nums[s]=1 → 相同 → f++ [0,1,1,1,1,2,2,3,3,4] s f 步骤4: f=4, nums[f]=1, nums[s]=1 → 相同 → f++ [0,1,1,1,1,2,2,3,3,4] s f 步骤5: f=5, nums[f]=2, nums[s]=1 → 不同 → s++, nums[s]=nums[f] [0,1,2,1,1,2,2,3,3,4] s f ... 以此类推，最终得到 [0,1,2,3,4]

3. 时间复杂度分析

• 时间复杂度: O(n)

  • 只需遍历数组一次

  • 每个元素最多被访问两次

• 空间复杂度: O(1)

  • 只使用两个指针变量

4. 边界情况处理

cpp

// 空数组 if (nums.empty()) return 0; // 单元素数组 // 直接返回1，无需任何操作 // 所有元素都相同 // slow始终为0，返回1

四、两种解法的对比

性能对比表

特性	迭代器+erase法	双指针法
时间复杂度	O(n²)	O(n)
空间复杂度	O(1)	O(1)
是否真正删除	是	否（只是覆盖）
代码复杂度	中等	简单
执行效率	低	高
适用场景	小数据量	所有场景

内存操作对比

cpp

// 方法一：erase操作的内存变化 [1,1,2,2,3] // 原始 [1,2,2,3] // 删除第一个重复1，移动后面3个元素 [1,2,3] // 删除重复2，移动后面1个元素 // 总共移动4个元素 // 方法二：双指针法的内存变化 [1,1,2,2,3] // 原始 [1,2,2,3,3] // 第一次复制（fast=2, slow=1） [1,2,3,3,3] // 第二次复制（fast=4, slow=2） // 没有元素移动，只有覆盖操作

五、常见错误与陷阱

错误1：迭代器越界

cpp

// 错误的写法 while(it != nums.end()) { if(*(it) == *(it + 1)) { // 当it指向最后一个元素时，it+1越界 it = nums.erase(it); } ++it; }

错误2：逻辑错误

cpp

// 错误的写法 while(it != nums.end()) { if((*it) == *(it - 1)) { nums.erase(it); // 没有接收返回值，it失效 } ++it; // 使用失效的迭代器 }

错误3：未处理空数组

cpp

// 需要处理空数组 if (nums.empty()) return 0;

六、扩展思考

1. 如果数组未排序怎么办？

cpp

// 需要先排序，但会改变相对顺序 sort(nums.begin(), nums.end()); // 然后再去重

2. 如果允许每个元素最多出现两次怎么办？

cpp

class Solution { public: int removeDuplicates(vector<int>& nums) { if (nums.size() <= 2) return nums.size(); int slow = 2; // 从第三个元素开始 for (int fast = 2; fast < nums.size(); ++fast) { // 比较当前元素与slow-2位置的元素 if (nums[fast] != nums[slow - 2]) { nums[slow] = nums[fast]; ++slow; } } return slow; } };

3. 如果要去重并保留原顺序（未排序数组）？

cpp

// 使用哈希表记录已出现元素 int removeDuplicatesUnordered(vector<int>& nums) { unordered_set<int> seen; int slow = 0; for (int fast = 0; fast < nums.size(); ++fast) { if (seen.find(nums[fast]) == seen.end()) { seen.insert(nums[fast]); nums[slow] = nums[fast]; ++slow; } } return slow; }

七、实际应用场景

1. 数据库查询结果去重

sql

-- SQL中的DISTINCT类似于数组去重 SELECT DISTINCT column_name FROM table_name;

2. 日志分析

• 去除重复的日志条目

• 统计唯一IP地址

• 分析用户唯一访问量

3. 数据清洗

• 去除重复记录

• 整理有序数据集

• 准备机器学习训练数据

4. 内存优化

• 减少内存占用

• 提高缓存效率

• 优化数据处理流水线

八、性能测试

测试代码

cpp

void testPerformance() { // 生成测试数据：100万个有序整数，有大量重复 vector<int> nums; for (int i = 0; i < 1000000; ++i) { nums.push_back(i / 100); // 每个数字重复100次 } vector<int> nums1 = nums; vector<int> nums2 = nums; // 测试方法一 auto start = chrono::high_resolution_clock::now(); Solution().removeDuplicatesErase(nums1); auto end = chrono::high_resolution_clock::now(); auto duration1 = chrono::duration_cast<chrono::milliseconds>(end - start); // 测试方法二 start = chrono::high_resolution_clock::now(); Solution().removeDuplicatesTwoPointers(nums2); end = chrono::high_resolution_clock::now(); auto duration2 = chrono::duration_cast<chrono::milliseconds>(end - start); cout << "方法一（erase）用时: " << duration1.count() << "ms" << endl; cout << "方法二（双指针）用时: " << duration2.count() << "ms" << endl; }

预期结果

text

方法一（erase）用时: 约5000ms 方法二（双指针）用时: 约10ms

九、总结与建议

1. 算法选择建议

• 面试场景：优先展示双指针法，体现算法优化思维

• 小数据量：两种方法都可，erase法代码更直观

• 大数据量：必须使用双指针法

• 工程实践：优先考虑效率和可维护性

2. 学习要点

• 理解原地操作的含义和限制

• 掌握迭代器的正确使用方法

• 熟练应用双指针技巧

• 分析算法的时间空间复杂度

3. 类似题目推荐

1. 删除排序数组中的重复项 II（每个元素最多出现两次）

2. 移动零（将0移动到末尾，保持非零元素顺序）

3. 移除元素（移除特定值，返回新长度）

4. 合并两个有序数组

4. 最终建议

在实际编程和面试中，双指针法是解决这类问题的首选。它不仅效率高，而且思路清晰，代码简洁。理解并掌握这种思想，能够解决一大类数组操作问题。

记住：好的算法应该是高效且优雅的，双指针法正是这样的典范。