1. 项目概述一道经典的“去重排序”入门题如果你刚开始接触信息学奥赛OI或者C编程那么“明明的随机数”这道题几乎是一个绕不开的里程碑。这道题同时出现在《信息学奥赛一本通》、OpenJudge、洛谷等多个主流OJ平台题号可能不同但核心完全一致。它之所以经典是因为它完美地融合了算法竞赛中最基础、最核心的两个操作去重和排序。题目背景很简单明明生成了一堆随机整数现在需要你帮忙去掉其中重复的数字并把剩下的数字从小到大排好序输出。听起来是不是很简单但别小看它。这道题在NOIP2006普及组作为第一题出现考察的正是选手对基础数据结构和标准库函数的掌握程度以及最朴素的“模拟”思维能力。很多新手会在这里踩坑要么去重逻辑写复杂了导致超时要么对排序的理解不够导致结果错误。今天我们就来彻底拆解这道题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及在不同场景下的“最优解”是什么。无论你是用C、Java还是Python这篇文章都能给你提供清晰的思路和可直接“抄作业”的代码。2. 核心需求与解题思路拆解2.1 题目本质数据清洗与整理我们先抛开“明明”这个背景把问题抽象一下。题目给我们的输入是一个整数N代表接下来有多少个数字。N个整数这些数字是“随机”的意味着可能重复可能无序。我们需要完成的输出是一个整数M代表去重后还剩多少个不同的数字。这M个不同的数字按照从小到大的顺序依次输出。所以这道题的本质是一个数据清洗与整理的过程。它模拟了现实中非常常见的场景比如统计一份名单中不重复的姓名数量并按字母序排列或者分析一组实验数据中不同的观测值。解题的核心流程可以归纳为三步读入 - 去重 - 排序 - 输出。其中“去重”和“排序”的顺序是可以互换的两种思路各有优劣我们后面会详细分析。2.2 思路对比先排序后去重 vs. 利用集合特性对于新手来说最容易想到的思路可能是“先排序后去重”。因为排序后相同的数字会紧挨在一起我们只需要遍历一遍跳过和上一个数字相同的项就能轻松得到去重后的有序序列。这个思路非常直观符合人的思维习惯。然而在编程的世界里我们拥有更强大的工具——集合Set。集合是一种数据结构它有一个天然的特性自动去重。无论你往集合里插入多少个重复的元素它内部只会保留一个。如果我们使用的集合如C的std::set本身还是有序的那么它甚至能同时完成去重和排序两项工作。这就引出了两种主流的解题范式数组排序遍历去重法使用数组存储所有数字用sort函数排序然后手动遍历输出去重后的结果。这是最基础、最能体现算法本质的方法。集合Set法直接将所有数字插入到一个集合中集合会自动帮我们完成去重和排序最后直接输出集合内容即可。这种方法代码简洁不易出错。哪种更好对于这道题两者在时间和空间复杂度上都能轻松通过。但从学习和理解的角度我强烈建议初学者先掌握第一种方法因为它能让你清晰地看到“去重”和“排序”这两个独立步骤是如何运作的。掌握了基础再使用“集合”这种高级工具你才能明白它到底帮你省了哪些事。3. 核心细节解析与实操要点3.1 输入输出的格式陷阱这道题的输入输出格式非常标准但细节决定成败。输入部分第一行是一个整数N(1 ≤ N ≤ 100)。第二行是N个用空格隔开的整数每个整数的范围在1到1000之间。这里要注意题目虽然说是“随机数”但输入格式是确定的。在编写代码时务必确保能正确读取这N个数。一个常见的错误是使用cin连续读取时没有处理好换行符或者循环次数不对。输出部分第一行输出去重后数字的个数M。第二行输出这M个升序排列的数数字之间用一个空格隔开。这里有一个极易被忽略的坑最后一个数字后面不能有空格很多在线评测系统OJ对输出格式要求极其严格多一个或少一个空格都会导致“格式错误”。因此在输出时我们通常采用一个小技巧先输出第一个数字然后循环输出” ” 数字或者使用一个标志位来控制空格的输出。注意在处理输入时如果N的值可能为0虽然本题范围是≥1你的程序也应该有基本的健壮性。不过本题明确N≥1我们可以简化处理。3.2 排序算法的选择与使用排序是本题的核心操作之一。对于范围在100以内的数据量任何排序算法哪怕是低效的冒泡排序都能在瞬间完成。但既然我们学习编程就应该使用更高效、更通用的方法。在C中最推荐使用的是标准库中的std::sort函数。它位于algorithm头文件中其底层实现通常是快速排序的优化版本IntroSort平均时间复杂度为 O(N log N)对于本题数据量绰绰有余。#include algorithm // ... 假设有一个数组 arr 已经存储了 n 个元素 std::sort(arr, arr n); // 对数组前n个元素进行升序排序std::sort默认是升序排序。如果我们需要降序可以传入自定义的比较函数或者使用std::greaterint()。但在本题中升序正是我们需要的。使用std::sort的好处是简单、高效、不易出错。自己手写排序算法虽然能加深理解但在竞赛或实际开发中直接调用成熟稳定的库函数是更明智的选择。3.3 去重逻辑的两种实现在“先排序后去重”的思路中去重逻辑的实现是关键。这里介绍两种常见的写法方法一双指针/下标法原地去重思想这种方法模拟了“原地去重”的过程。我们使用一个下标k来指向“当前已去重序列”的末尾。如果数组为空则直接返回0。否则从第二个元素i1开始遍历。如果当前元素arr[i]不等于arr[k]即不等于已去重序列的最后一个元素说明这是一个新元素。我们将k向后移动一位然后把arr[i]的值赋给arr[k]。遍历结束后k1就是去重后元素的个数而arr[0]到arr[k]就是去重后的有序序列。这种方法没有使用额外的数组空间效率高是处理有序数组去重的标准方法之一。方法二直接遍历输出法这是一种更直接、更适合本题的方法。因为题目要求输出我们不必真的修改原数组。排序后直接输出第一个元素arr[0]。从第二个元素开始遍历如果当前元素arr[i]不等于上一个输出的元素可以用一个变量last记录就输出当前元素。在输出的同时计数即可。这种方法逻辑清晰代码简洁是解决本题的推荐写法之一。它避免了操作原数组可能带来的下标错误。4. 完整代码实现与逐行解析下面我将分别给出“数组排序”法和“集合(Set)”法的C完整代码并附上详细注释。你可以将代码直接复制到洛谷、OpenJudge等平台提交。4.1 方案一数组 std::sort 遍历输出这是最经典、最教学意义的解法适合初学者深刻理解流程。#include iostream #include algorithm // 引入sort函数 using namespace std; int main() { int n; int nums[100]; // 根据题目N最大为100定义足够大的数组 cin n; // 1. 读入数据 for (int i 0; i n; i) { cin nums[i]; } // 2. 排序 sort(nums, nums n); // sort(起始地址 结束地址的下一个) 默认升序 // 3. 输出结果 // 先输出去重后的数量。由于数组已排序我们通过遍历找出不重复的元素个数 // 也可以边输出边计数 int count 0; int last -1; // 初始化一个不可能出现的值用于记录上一个输出的数 // 第一次遍历计算个数M for (int i 0; i n; i) { if (nums[i] ! last) { count; last nums[i]; } } cout count endl; // 第二次遍历实际输出数字 last -1; // 重置last bool isFirst true; // 标志位用于控制空格输出 for (int i 0; i n; i) { if (nums[i] ! last) { if (!isFirst) { // 如果不是第一个数字先输出一个空格 cout ; } cout nums[i]; isFirst false; last nums[i]; } } // 输出换行符有的OJ要求有的不要求但加上是个好习惯 cout endl; return 0; }代码解析与避坑点数组大小题目明确N≤100但习惯上我们会稍微开大一点比如105防止边界错误。这里开100是精确值没问题。sort函数参数sort(nums, numsn)是对数组nums从第0个到第n-1个元素即前n个进行排序。numsn是最后一个元素的下一个地址这是STL函数常见的“左闭右开”区间约定。去重计数代码中遍历了两次数组第一次计数第二次输出。这完全是为了清晰展示两个步骤。实际上可以合并成一次遍历在输出数字的同时计数最后再输出计数。但注意题目要求先输出M再输出数字序列所以如果合并遍历需要先将去重后的数字暂存起来或者先计算M。空格处理使用isFirst标志位是处理输出格式的经典技巧。它确保了数字之间只有一个空格且末尾没有多余空格。4.2 方案二使用 std::set推荐对于已经了解STL的选手这是最简洁、最不易出错的解法。#include iostream #include set // 引入set容器 using namespace std; int main() { int n, temp; setint s; // 定义一个int类型的集合它会自动升序排序且去重 cin n; for (int i 0; i n; i) { cin temp; s.insert(temp); // 将所有数字插入集合重复的会被自动忽略 } // 输出结果 // 集合的大小就是去重后的数量M cout s.size() endl; // 遍历集合并输出元素 // set已经是有序的直接输出即可 bool isFirst true; for (auto it s.begin(); it ! s.end(); it) { if (!isFirst) { cout ; } cout *it; // it是迭代器*it取得它指向的值 isFirst false; } cout endl; // 更现代的C11及以上版本的遍历写法更简洁 // bool isFirst true; // for (int num : s) { // if (!isFirst) cout ; // cout num; // isFirst false; // } // cout endl; return 0; }代码解析与优势极致简洁核心逻辑只有读入、插入、输出。set容器帮我们隐藏了所有排序和去重的复杂细节。自动排序std::set底层通常使用红黑树实现插入元素的同时就维护了有序性无需额外调用sort。自动去重insert操作会检查元素是否已存在只有不存在时才插入。时间复杂度每次插入是 O(log N)总复杂度 O(N log N)和先排序后去重是一样的。对于本题数据量性能无差异。遍历使用迭代器begin()和end()遍历集合是标准做法。C11的范围for循环让代码更清晰。提示std::set虽然方便但它消耗的内存比数组略大因为要维护树结构并且常数时间开销也稍大。在极端追求性能的场景如数据量极大下数组排序法可能略有优势。但对于入门题和绝大多数情况set的可读性和可靠性优势更大。5. 常见错误与问题排查实录即便思路清晰新手在实现时也常会掉进一些坑里。下面是我在辅导学生和自己刷题时遇到的一些典型问题。5.1 输出格式错误多余的空格或换行这是最最常见的错误没有之一。OJ的判题机是逐字符比对输出的。错误示例1末尾多空格for (int i 0; i m; i) { cout ans[i] ; // 每次输出都带空格最后一个数字后也会多一个空格 }解决方法使用前面提到的“首次标志位”法或者先输出第一个元素之后循环输出” ” 元素。错误示例2缺少换行cout m; for (int i 0; i m; i) { ... } // 输出完数字后没有换行虽然有些OJ对末尾换行不敏感但严格来说题目描述中“第二行输出”就意味着第一行输出后要有换行整个输出结束后最好也有换行。加上cout endl;是好习惯。5.2 去重逻辑错误未排序直接去重这是对题意理解不深导致的。如果数组没有排序相同的数字可能分散在各处简单的相邻比较去重法就会失效。// 错误代码示例假设数组未排序 int last -1; for(int i0; in; i){ if(arr[i] ! last){ // 如果数组是 [2,1,2]last先变成2再遇到1时会输出但1之后又遇到2因为2!1又会输出导致去重失败。 cout arr[i] ; last arr[i]; } }解决方法务必先排序再去重。这是“数组法”的铁律。5.3 边界条件处理N1或所有数字都相同考虑边界情况是编程的好习惯。N1程序应该能正常处理。排序一个元素没问题去重逻辑中last的初始值如-1不应等于这个唯一的数字否则会计数错误。通常将last初始化为一个数据范围外的值如-1因为题目数字是1~1000是安全的。所有数字都相同例如输入5 1 1 1 1 1。程序应该输出1和1。你的去重逻辑需要能正确处理这种情况即遍历一遍后只计数一次只输出一次。5.4 使用Set时忽略迭代器用法对于初学者set的遍历可能有点陌生。必须使用迭代器不能像数组一样用下标s[i]访问。setint s; // ... 插入元素 // 错误cout s[0]; // set不支持下标运算符[] // 正确 for(setint::iterator it s.begin(); it ! s.end(); it){ cout *it ; } // 或者使用auto关键字C11 for(auto it s.begin(); it ! s.end(); it){ cout *it ; } // 或者使用范围for循环C11 for(int num : s){ cout num ; }5.5 数组越界如果题目说N最大100你只定义了int arr[100]那么有效的下标是0~99。在循环时务必确保i n且n 100。定义数组时稍微开大一点int arr[105]是个有效的防御性编程技巧。6. 算法扩展与性能思考虽然这道题数据量很小但我们不妨思考一下如果N变得非常大比如10^5甚至10^6我们的解法还适用吗6.1 时间复杂度的再分析数组排序法std::sort的时间复杂度是 O(N log N)后续的线性去重遍历是 O(N)。总复杂度为 O(N log N)对于百万级的数据在1秒内也能完成。Set插入法每次set.insert()操作是 O(log K)K为当前集合大小最坏情况下所有数字都不重复总复杂度也是 O(N log N)。虽然复杂度相同但由于红黑树每次插入都需要调整平衡其常数因子比快速排序的sort要大实际运行时间通常会比“数组排序法”慢一些。所以在纯粹追求运行速度的场合“数组排序法”是更优的选择。set的优势在于代码的简洁性和表达力。6.2 空间复杂度的考量数组法需要 O(N) 的数组空间。Set法同样需要 O(N) 的空间来存储节点但由于每个节点需要额外的指针左右孩子、父节点、颜色标志等其实际内存占用大约是数组法的2-3倍。对于内存限制严格的场景数组法更有优势。6.3 如果数字范围有限桶排序思想本题还有一个隐藏条件数字范围在1到1000之间。这是一个很小的范围。我们可以利用“桶排序”或“计数排序”的思想达到接近 O(N) 的时间复杂度。思路是创建一个大小为1001的布尔数组bool bucket[1001] {false};。读入每个数字x时将bucket[x]标记为true。读入完成后从1到1000遍历这个桶数组如果bucket[i]为真则i就是去重后的数字且由于遍历顺序是从小到大输出自然有序。#include iostream using namespace std; int main() { int n, x, count 0; bool bucket[1001] {false}; // 初始化所有桶为false cin n; for (int i 0; i n; i) { cin x; if (!bucket[x]) { // 如果这个数第一次出现 bucket[x] true; count; // 计数 } // 如果已经出现过什么也不做 } cout count endl; bool isFirst true; for (int i 1; i 1000; i) { // 题目范围是1~1000 if (bucket[i]) { if (!isFirst) cout ; cout i; isFirst false; } } cout endl; return 0; }这种方法的时间复杂度是 O(N K)其中K是数值范围这里是1000。当N很大比如10^5而K相对较小时这种方法比基于比较的排序 O(N log N) 要快得多而且是稳定的 O(N) 解法。它同时完成了去重和排序代码也非常简洁。这是利用数据特性进行优化的经典案例。7. 在不同OJ平台的提交注意事项这道题在多个平台都有收录虽然核心代码一样但不同平台的输入输出格式、题面描述可能略有差异提交时需要注意。洛谷 P1059题目描述清晰标准输入输出。使用上述任一种代码均可通过。注意洛谷的在线编辑器对换行符不敏感但养成输出最后换行的习惯总是好的。OpenJudge 1.10 09OpenJudge的题目有时来自不同题库格式要求严格。务必检查样例输出的每一个空格和换行。建议提交前在本地多次运行对比输出和样例是否完全一致可以复制粘贴到文本比较工具中查看。信息学奥赛一本通 1184这本书配套的在线评测系统通常也比较标准。注意该书可能更倾向于考察学生对基础算法的实现使用“数组排序法”可能更贴合其教学目的。一个通用的提交前自查清单编译是否通过检查头文件、语法错误。样例输入是否能得到完全一致的输出仔细比对包括空格和换行。考虑边界情况了吗输入N1N100所有数相同所有数都不同等情况自己测试一下。变量名是否清晰虽然不影响结果但清晰的变量名有助于调试。是否删除了调试用的中间输出确保最终提交的代码只输出题目要求的内容。这道“明明的随机数”就像编程路上的一个老朋友简单却内涵丰富。它考察的排序和去重是数据处理中最基本的操作。从最朴素的数组排序遍历到利用STLset的优雅实现再到利用值域范围的桶排序一道题背后是算法思维层层递进的体现。对于初学者我建议你亲手实现一遍“数组排序法”理解每一个步骤当你熟悉之后set会成为你工具箱中一件高效的利器而最后提到的“桶排序”思想则展示了如何利用数据特性进行降维打击这种思维在解决其他问题时也极其宝贵。编程的学习就是这样从一个简单的问题出发不断挖掘更深层次的方法和优化思路乐趣和成长就在其中。