C++去重排序算法详解：从数组到STL的四种实现方案

1. 项目概述：一道经典的“去重排序”入门题

如果你刚开始接触信息学竞赛，或者正在学习C++、Java等编程语言的数据结构基础，那么“明明的随机数”这道题几乎是一个绕不开的里程碑。它频繁出现在《信息学奥赛一本通》、OpenJudge、洛谷等各大OJ平台，题号可能不同，但核心完全一致。我第一次接触这道题时，觉得它简直是为初学者量身定做的“完美练习题”——它不涉及复杂的算法思想，却巧妙地串联起了数组操作、排序和去重这几个最基础、最核心的编程概念。

这道题描述了一个非常生活化的场景：明明生成了N个1到1000之间的随机整数，现在需要你帮忙完成“去重”与“排序”两项工作。最终输出两个结果：第一行是去重后剩余不同数字的个数，第二行是这些数字按从小到大排序后的序列。题目本身简单直接，但正是这种简单，让它成为了检验你是否真正掌握基础数据处理能力的试金石。很多同学在学习了sort函数和set集合后，会觉得这道题索然无味，但你是否想过，如果不允许使用STL库，你能否仅用数组和基本循环就优雅地解决它？这道题的价值，恰恰在于它逼迫你去思考数据处理的本质。

2. 核心需求与解题思路拆解

2.1 问题本质：数据清洗与整理

我们抛开“明明”这个背景，将问题抽象一下：你手头有一批可能存在重复的数据（整数），你的任务是对这批数据进行清洗，剔除重复项，然后按照一定的规则（这里是升序）进行整理输出。这在实际编程中太常见了，比如统计用户ID、处理日志中的IP地址、分析商品编号等。题目将数据范围限定在1-1000，且N≤100，这个设定非常友好，意味着我们可以使用一些“朴素”但高效的方法。

2.2 核心步骤分解

无论采用哪种方法，解决这个问题的逻辑流程都可以分解为以下三步：

1. 输入与存储：读取整数N，然后循环N次读取随机数，将它们存入一个容器（如数组、向量或集合）。
2. 去重与排序：这是算法的核心。需要消除容器中的重复元素，并将剩余元素按升序排列。注意，去重和排序的顺序可以互换，不同的顺序会衍生出不同的解题策略。
3. 输出结果：第一行输出去重后的元素个数M，第二行输出这M个已排序的元素，用空格隔开。

2.3 方法选型背后的考量

为什么这道题会有多种解法？因为它处于一个复杂度与代码量的“甜蜜点”。数据量小（N≤100，数值范围1-1000），使得从O(N²)到O(N log N)甚至O(N)的算法都在可接受范围内。这就允许我们根据不同的学习阶段和编程语言特性，选择最合适的工具：

• 初学者/巩固基础：应优先使用数组和基本循环，手动实现去重和排序（如冒泡排序+遍历去重），这能深刻理解过程。
• 掌握STL的C++选手：使用sort和unique函数组合，是比赛中最快捷、不易出错的“标准答案”。
• 利用数据结构特性：直接使用set或unordered_set（后去重），其自动排序和去重的特性让代码极其简洁。
• 利用数值范围：使用“桶”的思想（标记数组），可以达到理论上的O(N)时间复杂度，这是一种空间换时间的典型思路。

选择哪种方法，取决于你的目的。如果是练习，我强烈推荐从数组手动实现开始；如果是竞赛中快速解题，那么sort+unique或set是不二之选。

3. 四种经典实现方案详解

下面我将分别用四种典型的C++实现方案来解析这道题，并附上详细的注释和对比。你可以清晰地看到从“底层实现”到“高级抽象”的演进过程。

3.1 方案一：纯数组 + 手动冒泡排序与去重

这是最“原始”的方法，不依赖任何现成的库函数，适合初学者理解每一个步骤。

#include <iostream> using namespace std; int main() { int n; int nums[101]; // 根据题意，N最大为100，多开一个位置防止越界 cin >> n; // 1. 输入数据 for (int i = 0; i < n; i++) { cin >> nums[i]; } // 2. 排序（这里使用冒泡排序，易于理解） for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (nums[j] > nums[j + 1]) { // 交换 int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } // 3. 去重并统计个数 int m = 0; // m用于记录去重后数组的有效长度，也作为新数组的下标 for (int i = 0; i < n; i++) { // 如果是第一个元素，或者当前元素不等于上一个有效元素，则保留 if (i == 0 || nums[i] != nums[m - 1]) { nums[m] = nums[i]; // 将不重复的元素移到数组前部 m++; } // 如果nums[i] == nums[m-1]，说明是重复元素，直接跳过，i++继续循环 } // 4. 输出结果 cout << m << endl; for (int i = 0; i < m; i++) { cout << nums[i] << " "; } cout << endl; // 输出换行，符合格式要求 return 0; }

核心要点与避坑指南：

• 数组大小：题目说N≤100，但数组最好声明为[101]或更大，这是一个良好的防越界习惯。
• 去重逻辑：这段去重代码非常经典。它利用了数组已排序的特性。m指针始终指向“去重后数组”的末尾下一个位置。当遍历原数组nums[i]时，只将与nums[m-1]（即当前去重数组最后一个元素）不同的元素追加到去重数组末尾。这个操作直接在原数组上进行，节省了空间。
• 为什么先排序再去重？对于无序数组，去重需要将每个元素与之前所有元素比较，复杂度为O(N²)。排序后，重复元素必然相邻，只需一次遍历O(N)即可完成去重，总复杂度取决于排序算法（冒泡为O(N²)）。先排序再去重是更优的策略。

3.2 方案二：C++ STLvector+sort+unique

这是竞赛中最常用、最规范的写法，兼具效率与简洁。

#include <iostream> #include <vector> #include <algorithm> // 包含sort和unique using namespace std; int main() { int n; cin >> n; vector<int> nums(n); // 直接初始化大小为n的vector for (int i = 0; i < n; i++) { cin >> nums[i]; } // 1. 排序 sort(nums.begin(), nums.end()); // 2. 去重。unique函数将不重复的元素移到前面，并返回去重后新序列的尾后迭代器 auto new_end = unique(nums.begin(), nums.end()); // 3. 计算去重后大小并输出 int m = new_end - nums.begin(); // 迭代器相减得到元素个数 cout << m << endl; // 4. 输出去重后的元素 for (auto it = nums.begin(); it != new_end; ++it) { cout << *it << " "; } cout << endl; return 0; }

核心要点与避坑指南：

• unique函数的行为：这是关键！std::unique并不会删除容器中的元素，也不会改变容器的size()。它只是将相邻的重复元素“移动”到容器末尾，并返回一个指向第一个被移动的重复元素（即新逻辑序列末尾）的迭代器。容器nums在unique之后，[begin(), new_end)区间是不重复的有序序列，而[new_end, end())区间是重复元素的“残留”，其值是不确定的。
• 如何真正删除元素？如果后续操作需要干净的容器，可以调用nums.erase(new_end, nums.end())。但本题只需输出，所以不需要erase。
• 迭代器计算个数：new_end - nums.begin()是得到去重后个数的标准写法，因为随机访问迭代器支持相减操作。

3.3 方案三：利用set自动去重排序

这是代码最简洁的方案，充分利用了STL容器的特性。

#include <iostream> #include <set> using namespace std; int main() { int n, temp; cin >> n; set<int> s; // set会自动排序（默认升序）且去重 for (int i = 0; i < n; i++) { cin >> temp; s.insert(temp); // 插入操作，重复元素不会被插入 } // 输出 cout << s.size() << endl; // 大小即为去重后个数 for (auto it = s.begin(); it != s.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }

核心要点与避坑指南：

• set的底层与复杂度：set通常基于红黑树实现，每次insert操作的复杂度是O(log N)，总复杂度为O(N log N)。虽然和sort一样，但常数可能略大。对于本题数据量，完全无感。
• unordered_set不行：如果你想用unordered_set（哈希集合）来只去重，会发现它不保证元素顺序，输出时还需要额外排序，反而不如set方便。
• 简洁性的代价：此方法代码量最小，逻辑最清晰。但在一些对性能极其苛刻或禁止使用STL的场景下，需要回到方案一或方案四。

3.4 方案四：“桶排序/标记法”思路

这是一种非常巧妙的O(N)方法，利用了题目中“随机数是1到1000之间的整数”这个限定条件。

#include <iostream> using namespace std; int main() { int n, temp; cin >> n; bool bucket[1001] = {false}; // 下标1-1000，初始化为false，表示该数字未出现 int count = 0; // 1. 读入并标记 for (int i = 0; i < n; i++) { cin >> temp; if (!bucket[temp]) { // 如果这个数第一次出现 bucket[temp] = true; // 标记为已出现 count++; // 统计不同数字的个数 } // 如果已经为true，说明重复，忽略 } // 2. 输出个数 cout << count << endl; // 3. 输出数字（天然有序，因为我们是按下标1-1000遍历的） bool first = true; // 用于控制空格输出，第一个数前不输出空格 for (int i = 1; i <= 1000; i++) { if (bucket[i]) { if (!first) { cout << " "; } cout << i; first = false; } } cout << endl; return 0; }

核心要点与避坑指南：

• 空间换时间的典范：我们创建了一个大小为1001的布尔数组（“桶”），下标对应数字本身。读入数字temp时，直接将bucket[temp]标记为true。这个过程同时完成了去重（重复标记无效）和排序（输出时只需从1到1000遍历，值为true的就输出，顺序自然是升序）。
• 时间复杂度：读入和标记O(N)，输出遍历O(1000)，总复杂度O(N+1000)，对于本题范围，几乎是线性时间。
• 局限性：此方法严重依赖数据范围小且已知的前提。如果数字范围是-10^9到10^9，这种方法将因需要巨大空间而不可行。但它完美契合了本题条件，展示了根据数据特征选择算法的智慧。
• 输出格式技巧：使用first标志位来控制空格的输出，避免了末尾多空格的常见格式错误，比在循环内判断i是否最后一个有效数字更简洁。

4. 方案对比与场景选择

为了更直观地理解四种方案的差异，我整理了下面的对比表格：

个人经验与选择建议：在我的刷题和教学经验中，对于这道题：

1. 如果你是初学者，请务必亲手实现一遍方案一。这个过程能让你透彻理解“排序”和“去重”这两个基本操作是如何在内存中一步步完成的。这是内功，绕不开。
2. 当你准备参加考试或竞赛，方案二是你的首选。它平衡了效率、代码量和可读性，是专业选手的标配。务必熟练掌握sort和unique的配合。
3. 当你在开发中快速实现一个小功能，或者在做题追求最短代码时，方案三用set是最舒服的。
4. 当你看到题目数据范围很小（比如本题1-1000），一定要想到方案四。这是一种典型的“桶”或“哈希”思想，在特定条件下威力巨大，能帮你写出时间复杂度最优的代码。

5. 常见错误与调试技巧实录

即便是一道简单题，新手也容易踩坑。下面是我从大量学生提交的代码中总结出的高频错误点。

5.1 格式错误：多余的空格或换行

这是OJ判题最常见的错误之一。题目要求第二行数字间用空格隔开，但行末不能有多余空格。

错误示例：

for (int i = 0; i < m; i++) { cout << nums[i] << " "; // 这样会在最后一个数字后面也输出一个空格 }

正确写法（多种）：

• 方法A：第一个元素特殊处理

  cout << nums[0]; for (int i = 1; i < m; i++) { cout << " " << nums[i]; }

• 方法B：使用标志位（如前文方案四所示）
• 方法C：使用条件判断（适用于知道最后一个元素下标的情况）

  for (int i = 0; i < m; i++) { if (i > 0) cout << " "; // 不是第一个就先输出空格 cout << nums[i]; }

5.2 去重逻辑错误

在手动实现时，去重逻辑写错，导致漏掉某些情况或数组越界。

错误示例1：未排序就去重，或去重逻辑只比较相邻元素但数组未排序。错误示例2：使用双重循环去重时，在删除元素（或覆盖元素）后，循环变量处理不当，导致跳过元素或访问越界。

建议：对于初学者，最稳妥的方法是先排序，再用一个循环和单个指针进行去重（如方案一所示），这个逻辑最清晰，不易出错。

5.3 对unique函数的误解

以为unique之后容器的size()就变了，直接遍历整个容器输出。

错误示例：

unique(nums.begin(), nums.end()); cout << nums.size() << endl; // 错误！size()没有变 for (int num : nums) { // 错误！会输出残留的重复元素 cout << num << " "; }

牢记：unique返回的是新的逻辑结尾迭代器，物理容器大小不变。必须用返回的迭代器来计算个数和界定输出范围。

5.4 数组越界

声明数组int a[100]，但循环时for (int i=0; i<=n; i++)或者cin >> a[i]时i可能等于n。养成习惯，数组大小声明为N+10是一个有效的防御策略。

5.5 调试技巧

1. 小数据测试：自己构造包含重复、无序、边界值（如N=1，所有数相同，所有数都不同）的测试数据。
   • 输入：5 [1, 2, 2, 3, 1]
   • 预期输出：3\n1 2 3
2. 输出中间变量：在排序后、去重后，分别打印整个数组，观察数据变化是否符合预期。
3. 使用在线调试器：像洛谷、Codeforces等平台都提供简单的在线调试功能，可以单步执行查看变量值。
4. 对比输出：将你的程序输出与已知正确的程序输出（或手算结果）进行逐行对比，能快速定位问题出在个数统计还是序列输出上。

6. 从本题延伸的编程思维训练

“明明的随机数”的价值远不止于AC一道题。它像一颗种子，能延伸出许多重要的编程思维和技能点。

6.1 理解“空间换时间”与“时间换空间”

方案四（桶标记法）是典型的“空间换时间”。我们用了1001个布尔变量的空间，换来了接近O(N)的线性时间。反之，如果内存极其紧张，我们可能需要在时间上进行妥协。这种权衡在算法设计中无处不在，比如哈希表（空间换时间）和链表（节省空间但访问慢）。

6.2 掌握数据处理的“管道”思想

这道题的解决过程像一个数据处理管道：原始数据 -> 排序 -> 去重 -> 输出。在现代数据处理框架（如Python的pandas，数据库的SQL）中，这种“声明式”的链式操作非常普遍。sort和unique的组合，就是这种思想的体现。你可以思考，如果需求变成“去重 -> 排序”或者“只去重不排序”，管道应该如何调整？

6.3 举一反三：变种题目

当你熟练掌握本题后，可以尝试解决它的变种，巩固知识：

• 去重但不排序：输出去重后的元素，但保持它们在原序列中的第一次出现顺序。这需要你用unordered_set记录出现过的元素，并用另一个vector保存顺序。
• 统计每个数的出现次数：这就不再是简单的去重，而是“计数”。桶标记法可以轻松升级为int bucket[1001]来计数。
• 大数据范围去重排序：如果数字范围是-10^9到10^9，但N只有10^5，你还能用桶吗？这时set或sort+unique依然是可靠选择，你需要理解算法适用范围的变化。

6.4 编码习惯与鲁棒性

即使题目简单，也要写出健壮的代码。比如：

• 数组开大一点：int nums[110]比int nums[100]更安全。
• 变量命名清晰：用unique_end而不是it，用count而不是c。
• 处理输入边界：虽然本题保证N>0，但养成习惯，考虑如果N=0程序是否会崩溃。

这道“明明的随机数”就像编程世界里的“Hello World”之后的第一道关卡，它平静地站在那里，检验着你是否真的准备好了处理数据的基本功。我见过很多同学为了追求刷题量，直接用set一行代码AC后就匆匆离开，这非常可惜。停下来，用几种方法都实现一遍，思考其中的差异，你会收获的远不止一个绿色的“Accepted”标志，而是对程序如何操作数据的一种扎实的、直觉性的理解。这种理解，会在你未来面对更复杂的字符串处理、图论建模、动态规划状态设计时，悄然发挥巨大的作用。