C++原地删除有序数组重复项的N种方法

前言「原地删除有序数组中的重复项」是 LeetCode 26 题。给定一个按非递减顺序排列的数组要求在每个元素最多保留一次的前提下把去重后的元素放到数组前部返回新的长度 k。判题系统只检查前 k 个元素k 之后的内容不参与比较但要求不能使用额外的数组空间。这道题的「有序」是解题的关键。数组有序意味着相同的值一定相邻因此不需要哈希表记录「见过谁」只需要比较当前元素和前一个保留下来的元素。如果数组无序原地去重在不排序的前提下无法用 O(1) 额外空间完成——这是题目给有序条件的原因。常见错误有三类用std::set或额外数组虽然结果对但违反空间要求在循环里反复erase每次搬移尾部整体退化成 O(n²)返回nums.size()而不是新的长度或者覆盖时读写指针的边界写错。本文给出快慢指针、std::unique和泛型写法三种实现并说明它们的关系。一、约束与返回值的含义LeetCode 的函数签名是// 适用于 C17int removeDuplicates(std::vectorint nums);返回值 k 表示去重后元素个数。判题系统会用 k 截取前 k 个元素再与期望数组比较。因此函数必须保证前 k 个位置存放的是去重后的元素且保持原顺序k 之后的元素是什么无所谓但不能越界写额外空间是 O(1)不能新建一个等长数组。第 3 条是「原地」的含义。用std::vectorint out;存结果再拷回去空间是 O(n)不符合要求用std::set更糟既费空间又丢了有序性带来的线性时间。二、方法一快慢指针维护两个下标slow指向「已写入的最后一个位置」fast从头遍历。因为数组有序只需比较nums[fast]和nums[slow]不同就说明遇到了新值把它写到slow 1并推进slow。// 适用于 C17#include cstddef#include vectorint removeDuplicates(std::vectorint nums) {if (nums.empty()) return 0;std::size_t slow 0; // 最后一个已保留元素的下标for (std::size_t fast 1; fast nums.size(); fast) {if (nums[fast] ! nums[slow]) {slow;nums[slow] nums[fast]; // 覆盖到前部}}return static_castint(slow 1);}以[1, 1, 2, 3, 3]为例步骤fastnums[fast]nums[slow]动作slow初始111相同跳过01221不同写入 nums[1]212332不同写入 nums[2]323433相同跳过2最终slow 2返回 3前三个元素是[1, 2, 3]。时间复杂度 O(n)每个元素读一次空间 O(1)。fast从 1 开始是因为第一个元素必然保留。返回类型是int而slow 1是std::size_t需要显式转换。题目保证数组长度在int范围内转换安全但在通用代码里应确认这个前提。三、方法二std::uniquestd::unique(first, last)把相邻的重复元素「移走」保留每段重复的第一个返回新的逻辑结尾。它同样是原地操作不改变容器大小// 适用于 C17#include algorithm#include iterator#include vectorint removeDuplicatesUnique(std::vectorint nums) {const auto new_end std::unique(nums.begin(), nums.end());return static_castint(std::distance(nums.begin(), new_end));}std::unique的语义是「删除相邻重复」对有序数组而言所有重复都相邻效果就是全局去重。若数组无序它只会删掉连续出现的重复值结果不是去重。这一点必须和std::remove区分后者按值删除前者按相邻相等删除。std::distance对随机访问迭代器是 O(1)返回difference_type有符号。转换成int前要确认长度范围。这个方法代码最短语义最清晰前提是允许使用标准算法。面试若要求手写仍然要会快慢指针版本。四、方法三泛型写法把元素类型和比较方式抽出来可以写成模板适用于std::string、自定义结构体等// 适用于 C17#include cstddef#include functional#include utility#include vectortemplate typename T, typename Equal std::equal_toTstd::size_t uniqueInPlace(std::vectorT data, Equal eq Equal{}) {if (data.empty()) return 0;std::size_t write 0;for (std::size_t read 1; read data.size(); read) {if (!eq(data[read], data[write])) {write;data[write] std::move(data[read]);}}return write 1;}这里用std::move把元素移到前部对std::string这类持有堆内存的类型可以避免一次深拷贝。移动之后data[read]处于有效但未指定状态后续不会再读它所以安全。write始终小于等于read覆盖不会破坏尚未读取的元素。三种方法的对比如下方法时间额外空间是否保序适用快慢指针O(n)O(1)是面试手写、通用std::uniqueO(n)O(1)是允许标准算法泛型模板O(n)O(1)是多种元素类型复用循环内eraseO(n²)O(1)是不推荐std::setO(n log n)O(n)是违反空间要求五、完整示例// 适用于 C17#include algorithm#include cstddef#include iostream#include vectorint removeDuplicates(std::vectorint nums) {if (nums.empty()) return 0;std::size_t slow 0;for (std::size_t fast 1; fast nums.size(); fast) {if (nums[fast] ! nums[slow]) {slow;nums[slow] nums[fast];}}return static_castint(slow 1);}void show(const std::vectorint nums, int k) {std::cout k k [;for (int i 0; i k; i) {if (i ! 0) std::cout ,;std::cout nums[static_caststd::size_t(i)];}std::cout ]\n;}int main() {std::vectorint a{1, 1, 2};const int ka removeDuplicates(a);show(a, ka); // k2 [1,2]std::vectorint b{0, 0, 1, 1, 1, 2, 2, 3, 3, 4};const int kb removeDuplicates(b);show(b, kb); // k5 [0,1,2,3,4]std::vectorint c;const int kc removeDuplicates(c);show(c, kc); // k0 []return 0;}按标准语义输出依次是k2 [1,2]、k5 [0,1,2,3,4]、k0 []。空数组时函数直接返回 0不会访问nums[0]。对于 k 之后的残留元素示例没有清理也不应该依赖它们的值。常见坑点1. 返回原数组长度❌return static_castint(nums.size());—— 返回的是去重前的长度判题系统会多比较重复元素。✅ 返回slow 1或std::unique与begin()的距离。2. 空数组访问首元素❌std::size_t slow 0;后直接读nums[slow]不判空 —— 空数组时越界。✅ 函数开头if (nums.empty()) return 0;。3. 循环内反复 erase❌for (i 1; i nums.size(); i) if (nums[i] nums[i-1]) nums.erase(nums.begin()i);—— 每次搬移尾部整体 O(n²)且删除后下标错位。✅ 用快慢指针一次遍历覆盖最后不需要真的删除尾部。4. 读写指针含义混淆❌ 用nums[fast] ! nums[fast-1]判断后写入nums[fast]—— 写回原位等于没覆盖。✅ 写指针用slow读指针用fast比较对象是nums[slow]最后一个保留值。5. 用std::set去重❌std::setint s(nums.begin(), nums.end());再拷回 —— 额外 O(n) 空间违反原地要求。✅ 利用有序性用双指针空间 O(1)。6. 以为std::unique能处理无序数组❌ 对[1,2,1]调用std::unique后认为得到[1,2]—— 实际仍是[1,2,1]因为它只删相邻重复。✅ 先排序再用unique或改用哈希集合但那就不是原地了。7. 返回 k 但前 k 个未按顺序排列❌ 用「把重复项交换到末尾」的写法导致前 k 个元素顺序错乱。✅ 快慢指针覆盖保持原相对顺序判题系统按顺序比较。8. 有符号与无符号混用❌for (int i 1; i nums.size(); i)——int与size_t比较触发符号警告极大长度下可能出错。✅ 下标统一用std::size_t返回时再显式转int。总结要点结论前提数组有序重复值相邻核心读指针找新值写指针维护结果区时间O(n)每个元素访问一次空间O(1)不新建数组返回新长度 k前 k 个有效推荐面试手写快慢指针工程可用std::unique这道题是「双指针」最纯粹的形式一个指针读、一个指针写读指针永远不落后于写指针。理解这一点就不会写出「删除后下标错位」或「反复 erase」的版本。有序条件不是装饰它把「判断是否重复」从「查表」降成了「看前一个元素」这才是 O(1) 空间解法成立的根本原因。