“3338【例58.1】 明明的随机数”这道题算是入门算法里非常经典的一道“去重排序”例题。第一次见到它的人多半是刚学完数组和循环翻开某本入门教材时看到的。题目设定很朴素生成N个随机数把重复的去掉再从小到大排好。看起来简单但真正动手写代码时很多初学者会卡在“如何高效去重”和“如何处理输入输出”上。我平时给零基础的同学讲排序这一章时也喜欢拿这道题开场因为它能把桶排序、普通排序、STL容器这几个知识点串起来一道题吃透后面好几类题目都不怕了。这篇文章就围绕这道题把三种主流解法从头到尾拆开讲清楚包括每种写法背后的取舍、容易踩的坑、以及从这道题能延伸出去的知识点。无论你是刚接触编程的初学者还是在准备竞赛/算法面试的选手这道题的几种思路都值得慢慢消化。1. 题目到底在考什么——先从需求拆起1.1 读懂题目的三个关键点先看题面明明生成了N个1到1000之间的随机整数重复的数字只保留一个然后从小到大排序输出第一行输出去重后的数字个数M第二行输出这M个排好序的数字。这里隐含了三个考点。第一个考点是去重。输入数据里会有重复值你要想清楚“保留一个”到底意味着什么。很多同学第一次写直接用两层循环逐个比较重复就跳过去这种做法虽然能过但时间复杂度是O(N²)数据量一大就不好看。更聪明的做法是用空间换时间让数据自己告诉我们它出现过没有。第二个考点是排序。题目要求从小到大输出这里可以直接用现成的排序函数也可以自己写排序算法。关键在于你要意识到排序和去重的先后顺序会影响代码的复杂度。先排序再去重只需要比较相邻元素先乱序去重再排序通常需要一个标记数组或哈希表。第三个考点是输出格式。这里的输出要分两行第一行是去重后的个数第二行才是数字序列而且末尾有没有多余空格不同OJ或判题系统要求不一样。很多人代码逻辑没问题最后挂在输出格式上这个我后面会专门说。1.2 为什么这道题适合用来学算法我先说个实在话这道题本身不难但它是一块很好的“试金石”。它考察你对数组下标的理解、对标记思想桶/计数的掌握、对排序函数和容器用法的熟悉程度。如果一个人能不看题解独立写出桶排序解法和排序去重解法并且把两种解法的适用场景说清楚那他的基础就已经相当扎实了。从教学角度看这道题还可以引出“数据范围决定算法”的思路。题目给的数字范围是1到1000非常小所以桶排序是最优解。但如果数字范围变成10的9次方桶排序就不行了得换成排序或哈希表。这就是算法竞赛里常说的“看数据范围选算法”这道题就是最典型的第一课。2. 三种解法逐一拆解2.1 解法一桶排序/计数排序——最推荐入门者掌握桶排序的思路特别直白既然数字范围只有1到1000那我就开一个长度为1001的数组下标0到1000用它的下标来对应原始数字。遍历输入数据时每遇到一个数字x就把下标为x的位置标记成true表示“这个数字出现过”。最后再从头到尾扫描这个标记数组哪些位置是true就输出对应下标。这个思路本质上就是“用一个bool数组当作桶把数据扔进对应的桶里”。因为数组下标天然有序所以扫一遍就是排序后的结果因为重复的数据只会反复标记同一个位置所以去重也一起完成了。一箭双雕。#include bits/stdc.h using namespace std; int main() { int n, x; cin n; bool vis[1001] {false}; // 标记数字是否出现过下标对应数字本身 int cnt 0; // 记录去重后的个数 for (int i 0; i n; i) { cin x; if (!vis[x]) { // 这个数第一次出现 vis[x] true; cnt; } } cout cnt endl; for (int i 1; i 1000; i) { if (vis[i]) { cout i ; } } cout endl; return 0; }很多人第一次看这段代码会困惑为什么循环输出的时候直接从1开始不从0开始因为题目给的随机整数范围是1到10000不在范围内所以从1扫到1000就够了。如果你偷懒从0开始扫也没事反正vis[0]永远是false但养成根据题意控制循环边界的习惯更好。这段代码的时间复杂度是O(N 1000)其中1000是固定的扫描开销。这意味着输入数据量N可以继续变大但只要数值范围不变整体开销就基本是线性的。空间复杂度是O(1001)一个固定大小的bool数组几乎可以忽略不计。2.2 解法二排序相邻去重——不依赖数据范围桶排序虽好但它有一个致命前提——数据范围不能太大。如果题目把随机整数的范围改成1到10亿你不可能开一个长度为10亿的bool数组那会直接爆内存。这时候就需要第二种思路把数字读进数组先排序让所有相同的数字靠在一起然后只保留每段相同数字的第一个。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); // 先排序 vectorint result; // 存放去重结果 for (int i 0; i n; i) { if (i 0 || a[i] ! a[i - 1]) { result.push_back(a[i]); // 与上一个数不同说明是第一次出现 } } cout result.size() endl; for (int i 0; i result.size(); i) { cout result[i] ; } cout endl; return 0; }这里的核心判断条件是a[i] ! a[i-1]。因为排序之后重复的数字必然紧挨着所以只要当前数字和前一个数字不一样就说明它是这个数字第一次出现直接收集起来。为什么特判i 0因为第一个元素没有前一个元素可以比较它肯定是新出现的所以无条件保留。这个解法的时间复杂度由排序决定C的sort用的是快排或更复杂的混合排序平均复杂度是O(N log N)。当N很大的时候这个解法比桶排序更通用因为它只关心输入数据的个数完全不在乎数据值域有多大。代价就是比桶排序多了一次排序也多了存储结果数组的空间。2.3 解法三STL极简写法——利用unique去重如果你已经熟练掌握了STL那还可以写得更短。核心思路还是一样先sort排序再用unique把相邻重复的元素移动到容器末尾并返回新逻辑结尾的迭代器最后用erase把后面那些重复的垃圾元素删掉。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); cout a.size() endl; for (int i 0; i a.size(); i) { cout a[i] ; } cout endl; return 0; }unique函数把相邻的重复元素“挤”到数组末尾但它不会真的删除这些元素只是返回一个新的逻辑结尾位置。必须配合erase才能真正把这些多余的元素从vector里清掉。这一步如果不理解很容易写出“结果对但数组size不对”的尴尬代码。这种写法很简练适合竞赛选手在时间紧张时快速提交。但我不建议零基础的人一开始就只背这种写法。我见过不少同学能顺利默写sort unique erase但你问他“unique到底做了什么”却答不上来这样一旦题目条件变化就不会举一反三了。所以我的建议是先完全理解2.1和2.2再把2.3当作“更高阶的工具”来掌握。2.4 三种解法的对比与选择解法核心思路时间复杂度空间复杂度优点适用场景桶排序用数组下标记录出现次数O(N V)V为值域O(V)代码简单天然有序数值范围小且已知排序相邻去重排序后保留相邻首个元素O(N log N)O(N)不依赖值域通用性强数据范围大或不确定STL写法sort unique eraseO(N log N)O(N)代码量少不易手写出错熟练STL的选手这里V表示数值范围。如果你在考场上一眼看出数值范围只有几百或几千直接用桶排序它是所有解法里最快的。如果数值范围大、内存放不下就老老实实用排序。从做题策略上讲能快速判断“用哪种解法”往往比能写出多种解法更重要。3. 实操中容易踩的坑与排查心得3.1 输入输出格式的“隐形陷阱”这道题看起来简单但真实评测时因为格式WAWrong Answer的人不少。我挑几个最常见的翻车点。第一程序必须能处理多组测试数据吗有些OJ会把多个样例放在同一个输入文件里但如果题目没有特别说明通常只处理一组。不过这道题在不少教材里是单组输入。稳妥做法是先读入N再循环读N个数不写奇怪的循环条件这样单组多组都能自然处理。第二输出第二行那些数字时每个数后面跟一个空格但最后一个数后面能不能有空格严格说很多评测系统允许末尾空格但某些题目会用字符串比对多了个空格直接判错。最稳妥的办法是除了最后一个数其余数后面加空格或者全部数字后加空格然后最后单独输出一个换行。我个人习惯这样处理for (int i 1; i 1000; i) { if (vis[i]) { if (first) { cout i; first false; } else { cout i; } } }用first变量控制空格位置这样末尾绝不会多出多余空格。第三别忘输出完数字后要换行。有时候判题系统会对缺失的换行很敏感尤其是后面还有下一组数据时。3.2 数组越界和边界条件桶排序的标记数组大小我习惯开到1001也就是bool vis[1001]。为什么不是1000因为数组下标从0开始要能访问vis[1000]数组长度至少是1001。有些同学写成bool vis[1000]然后输入一个1000程序直接越界访问轻则输出乱码重则运行时崩溃。类似的如果题目数据范围是1到1000循环扫描时要从1到1000。我这里再强调一次所有边界都建议用题目给出的最大值如果题目说“1≤随机整数≤1000”那么vis[1000]就必须存在。3.3 输出个数与输出序列不一致还有一个常见问题是输出第一行的M和后面实际输出的数字个数对不上。比如有的同学在标记的时候用cnt统计但输出的时候循环条件写错少输出或多输出了一些数结果第一行的数字和第二行实际数量不一致评测时必然是WA。我的建议是在本地测试时可以先故意构造一组数据来验证例如输入 10 20 40 32 67 40 20 89 300 400 15它应该输出8 15 20 32 40 67 89 300 400个数是8数字也是8个。这种自测数据在初学阶段非常管用能帮你第一时间确认逻辑是否正确。3.4 本地测试与评测平台的差异处理还有一个实操经验有些同学在本地编译器里能跑一提交就报编译错误多是因为写了自己编译器支持但评测系统不支持的代码。比如#include bits/stdc.h在绝大多数竞赛评测平台都能用但在某些教学型平台的老编译器上可能不行。这种情况下改成标准的头文件集合更稳妥#include iostream #include vector #include algorithm using namespace std;别嫌麻烦吃一堑长一智。我自己带过的学生里至少有五六个因为贪图方便只用万能头文件结果在某个要求严格的环境里翻了车。提前把这些边缘问题解决掉比临时在考场上去猜要省心得多。4. 这道例题的延伸价值——从“会做题”到“会一类题”4.1 类似题目与解题套路“明明的随机数”只是“去重排序”这类问题的入门版。刷完它你可以顺手挑战几道同类型但形状不同的题。比如统计每个数字出现的次数并按照出现次数从高到低输出。这要求你在桶排序的基础上再排一次序。输入一串字符串去除重复字符并按字典序输出。思路一样只是从整数换成了字符。两个数组求交集或差集。可以先各自去重排序再使用双指针法一次扫描完成。这类题目的共同点是先想办法让数据“有序”然后所有关于重复、相邻、比较的操作都会变得很简单。如果你能把“明明的随机数”吃透后面遇到这些变体时分析路径几乎是完全一致的。4.2 从“去重排序”看离散化思想这道题还有一层更深的联系——离散化。所谓离散化就是当数据范围很大、但数据个数不多时我们不对数值本身建数组而是把原始数值映射成从1开始的连续整数。比如一组数[10000, 999999, 10000]映射成[1, 2, 1]然后就能用桶的思想处理。这个过程的第一步往往就是“排序去重”。所以你看这道题的“排序相邻去重”解法思路完全可以复用到一个看起来毫无关系的算法场景里。这就是为什么我强调理解写法背后的意义比背代码重要——因为你背的是“怎么对一个整数数组去重”但你真正需要掌握的是“如何制造有序性并利用有序性简化问题”。4.3 Python写法参考如果你不是竞赛党只是想用Python快速解决这个问题那就更简单了。Python的集合天然去重再配合排序函数几乎是一句话的事n int(input()) nums list(map(int, input().split())) result sorted(set(nums)) print(len(result)) print(*result)set(nums)利用哈希表去重sorted()排序*result把列表展开逐个输出。简洁是简洁但我还是建议你在学习阶段先用C的两种思路把底层逻辑做一遍再来用Python这种“作弊”方式。先懂原理再用工具和只会用工具完全不是一回事。5. 刷题效率与学习路径建议5.1 基础题怎么刷才有效很多初学者喜欢“刷题数量越多越好”但碰到这种简单题时往往一遍AC就扔到一边这样其实浪费了它的教学价值。一道好题至少要达到这几种状态才算消化掉不看任何代码自己默写桶排序解法并讲清楚为什么它能同时完成排序和去重。不看任何代码自己写排序相邻去重解法并解释为什么先排序再去重能简化问题。能说出两种解法的优缺点以及各自适用的数据范围。能手动模拟一段输入数据追踪代码执行过程指出哪个变量在哪一步发生变化。如果以上都做到了那这道题才算真正“过了”。我建议准备一个刷题本每道题记录三行用什么思路、为什么选这个思路、踩了什么坑。一个月后回头看你会发现自己的进步非常明显。5.2 用“费曼学习法”加深理解如果你发现自己老是记不住代码结构有个特别好用的小技巧把自己想象成老师对着一个完全不懂的人讲这道题。你可以讲为什么需要标记数组也可以讲unique函数做了什么。当你发现自己讲着讲着卡住了说明这个地方其实还没弄懂那就回头再看。这就是所谓的“费曼学习法”我觉得在算法入门阶段特别实用。我当年刚学这道题的时候卡在“为什么要先排序再去重”这里。后来我对着一个完全不写代码的同学把整个过程讲了一遍讲到自己突然意识到“排序让重复元素相邻这样只需比较前后两个位置复杂度直接降一个量级”那一瞬间才是真正通了。从那以后我再也没忘记过这个思路。5.3 考场上如何快速决策用哪种写法最后说点实战的。如果在竞赛考场或在线笔试里遇到这类题我通常提醒自己按三步走第一步看数据范围。如果数值范围很小比如这道题的1到1000直接桶排序。不要犹豫不要去写什么复杂结构最简单的方法往往是最稳的。第二步如果需要排序但数值范围大直接sort。很多学生纠结要不要手写快排、堆排我的建议是除非题目明确要求不允许使用库函数否则直接用库里的排序省时间、省错误率。手写排序的价值在于理解原理不在于考场炫技。第三步如果去重和排序同时出现优先考虑“排序后去重”的组合。这个套路在90%的题目里都成立只有极少数需要保序去重的场合才需要另想办法比如用哈希表记录是否出现过然后保持原始顺序输出。这个三步决策法我带过的学生用下来反馈都不错。它没有什么高深的东西就是把一个复杂问题拆成“看范围、选工具、定套路”三个简单动作在考场上能帮你把思考时间省下来不少。我个人现在写这类题其实更偏爱桶排序一眼扫到底的感觉。你不用去背任何花哨的模板只要牢牢记住一句话当你需要“去重排序”先把有序性拿在手里整个世界都会变简单。这是这道题教给我的最大收益希望学会这道题的你也能真正感受到这种“思路通了”的快感。