1. 从一场机试开始为什么“明明的随机数”总被安排在第一题第一次在机试系统里看到这道题时我忍不住笑了。“明明想在学校中请一些同学做问卷调查先用计算机生成了N个1到1000之间的随机整数再手动去重并排序最后按从小到大输出。”这不就是大学C语言作业期末考试原题吗但笑归笑这道题确实站在“大厂面试算法真题回忆176”这个位置上而且它出现的概率之高远超很多刷题者的预期。原因很简单机试第一题的核心逻辑从来不是选难题而是用一道“几乎所有人都会做”的题快速完成第一轮行为筛选——你稳不稳、细不细心、会不会在最简单的题上栽跟头。明明的随机数恰好具备这个属性它不考高深的数据结构不考复杂的边界处理但把随机数生成、数据去重、排序输出这三个基础操作缝在了一起任何一个环节马虎都能让整道题功亏一篑。我见过不少刷了几百道题的候选人在这道题上翻车原因五花八门有人忘了处理重复数字有人输出的最后一个元素后面多了个空格导致比对失败有人直接用了O(N²)的冒泡排序把本来秒过的题拖到超时。这不是能力问题而是对“简单题”的警惕心不够。所以今天这篇文章我想认真聊聊这道题。不仅给你能跑的代码更想带你把它的考察逻辑、多方案对比、易错点以及实际工程中的联想全都过一遍。无论你是刚开始刷算法题的新手还是准备校招、社招机试的候选人这道题都值得花半小时彻底吃透。2. 拆开题干看考点随机数、去重、排序一个不落2.1 “N个1到1000之间的随机整数”这句话的信息量先看题干的原始描述明明生成了N个1到1000之间的随机整数。这里的“随机整数”值得停顿一下。日常写代码用到的rand()、random()大多数时候生成的是伪随机数。比赛和机试系统里的测试数据其实是预先生成好、写死在测试文件里的“随机数”你的程序只需要把它们读进来处理即可不需要自己调用随机函数。但如果你是自己练习想在本地验证算法正确性就要真去生成随机数了。C里可以用std::mt19937配合uniform_int_distribution生成指定范围的随机整数Python则用random.randint(1, 1000)就能搞定。比如下面这段C代码#include iostream #include random using namespace std; int main() { mt19937 rng(random_device{}()); uniform_int_distributionint dist(1, 1000); int N 10; for (int i 0; i N; i) { cout dist(rng) ; } return 0; }你可能会问为什么范围偏偏选1到1000而不是1到10的9次方这是这道题第一个用心良苦的设计。数字范围只有1000个可能取值而N最大也只有100这意味着用布尔数组或者计数数组来处理去重和排序成本极低。反过来如果范围是10⁹那桶排序的数组就没法直接开那么大了。这个“范围有限”的提示其实就是考官在暗示你优先考虑空间换时间的做法。2.2 去重是核心诉求排序是输出要求再看题目的完整要求把随机整数去重后再从小到大排序输出。去重在前排序在后。这里有一个隐含的顺序逻辑如果你先排序再相邻去重效率和先哈希去重再排序几乎一样但如果你用桶/计数数组去重和排序会在同一个循环里自然完成连排序算法都省了。从这个角度看这道题真正想考察的其实是去重策略。对于参加过工作的人来说去重简直是每天都在做的操作数据库去重要加DISTINCT日志采集要按ID去重消息队列要保证至少一次语义下不重复消费。算法题里考的set、布尔数组、哈希表本质上都是这些工程手段的抽象模型。2.3 数据规模决定了算法选择的上限我们需要记住一句算法设计的核心原则没有脱离数据规模的“最优解”只有“在给定范围内最优”的解。这道题的N不超过100数字范围1到1000所以理论上任何复杂度都能过包括O(N²)的选择排序、冒泡排序。但“能过”和“好”是两回事。机试系统判题只是第一步后面的面试官可能会追问“你这个解法的时间复杂度是多少如果数据范围改成1到10⁹还能用桶排序吗如果N改成10⁵还能用这个思路吗”这时候你是不是真的理解了自己代码背后的权衡就暴露无遗了。所以不要因为题简单就只背代码把它当成一个复杂度分析的样本才更有价值。3. 四种解法横向对比从暴力到最优代码量和效率如何权衡这道题的解法很多网上随便一搜就能看到十几种。我结合自己刷题和面试的经验把最典型的四条路径放在一起做个对比。只有把方案全摆出来你才知道为什么桶排序是这道题的“最优解”。3.1 方案A读入后用布尔数组标记最后顺序扫描输出这是我最推荐的解法也是很多标准答案使用的思路。流程如下读入N。读入N个数字对每个数字x设置flag[x] true。从1到1000遍历flag如果为true就输出下标。这个方案的时间复杂度是O(N 1000)空间复杂度是O(1000)。在这个题的数据范围内它没有任何多余的比较、交换或删除操作去重和排序在一次遍历里同时完成。很多初学者会困惑这算什么排序它确实不是冒泡、快排那种“比较排序”而是属于非比较排序里的桶思想叫计数排序/桶排序的简化版也可以理解为给每个可能的取值开了一个“箱子”数字出现就把对应箱子标亮最后从1号箱扫到1000号箱亮了的箱子依次报数数字自然就是排好序的了。3.2 方案B先全部读入用排序算法排序再去重输出第二种常见方案是读入全部数字之后先做一次排序然后扫描排序后的数组跳过和前一个元素相同的元素只输出不重复的部分。在C里可以直接用std::sort加std::unique两行解决在Python里更是sorted(set(arr))一行搞定。这个方案的思路是先全局有序再相邻去重复杂度由排序算法决定排序O(N log N)去重O(N)总复杂度O(N log N)。胜在通用要是数字范围很大例如1到10⁹这种方案依然能扛得住。3.3 方案C用哈希表或集合容器即时去重还有不少同学喜欢用现成的容器比如C的setint、Java的TreeSet、Python的set。把数字一个个放进容器利用容器自身的唯一性约束去重最后输出时再排序或者直接用有序集合。这种方案代码最简洁但它隐藏了底层的数据结构实现如果面试官问“TreeSet的底层是什么”而答不上来反而会给自己挖坑。3.4 四方案横向对照表方案核心操作时间复杂度空间复杂度代码量通用性布尔数组标记标记顺序扫描O(N1000)O(1000)少需范围可预知排序去重sortuniqueO(N log N)O(N)少强有序集合容器set自动去重排序O(N log N)O(N)最少强哈希表手动排序unordered_setsortO(N log N)O(N)中强从表格可以看出来在这道题限定的数据范围内方案A在时间和空间上都完胜。但方案B和方案C的通用性更好如果以后遇到范围大到没法开数组的数字域你至少要能快速切换思路。我自己的习惯是数据范围小、可枚举果断用桶数据范围大、不可控就排序加去重。这个原则适用于绝大多数“去重排序”类题目。4. 手把手写代码核心实现与运行细节4.1 C桶排序实现最简单也最稳妥直接上代码。这里我把输入输出、边界处理和整个主流程写完整可以直接在编译器里跑通。#include cstdio int main() { int N; while (scanf(%d, N) ! EOF) { // 机试系统通常有多组输入建议写成循环 int flag[1001] {0}; // 下标1-1000初始全部为0 int x; for (int i 0; i N; i) { scanf(%d, x); flag[x] 1; // 数字x出现过打标记 } bool first true; // 用first控制空格输出避免末尾多余空格 for (int i 1; i 1000; i) { if (flag[i]) { if (!first) printf( ); printf(%d, i); first false; } } printf(\n); } return 0; }有几个地方我想特别强调。一是flag[1001]而不是flag[1000]因为数组下标从0开始而题目里的数字最多到1000如果你开flag[1000]执行flag[1000] 1就会越界这在严重的OJ上就是运行时错误RE。第二个是循环遍历输出时从i 1开始而不是从0开始因为数字范围是1到10000号位置用不上。第三是while (scanf(%d, N) ! EOF)这种写法有的机试系统一次只测一组数据那就不用循环但多组输入的情况非常常见写成循环更稳妥。这里用scanf而不是cin是因为scanf在大量输入时更快虽然对这道题来说差异可以忽略但养成良好的IO习惯没有坏处。4.2 Python实现两行代码背后的取舍如果你用Python刷题最直观的写法一定是import sys data list(map(int, sys.stdin.read().split())) if not data: exit() n data[0] nums data[1:1 n] result sorted(set(nums)) print( .join(map(str, result)))sys.stdin.read().split()一次性读入全部数据再切片取前N个数字然后sorted(set(nums))把去重和排序同时完成。代码量确实很小但注意这里有一个细节set返回的是无序集合所以你必须用sorted再排一次序如果你只写set(nums)直接打印输出顺序完全看哈希表的内部实现大概率不对。另一种更“算法化”的Python写法是模拟桶seen [0] * 1001 for x in nums: seen[x] 1 out [str(i) for i in range(1, 1001) if seen[i]] print( .join(out))这个写法等价于C的桶排序关键在于列表推导式的条件部分if seen[i]只收集标记为1的下标天然完成了从小到大的遍历。两种Python写法都能AC但你要知道它们背后的复杂度是一样的区别只在于set sorted更依赖Python内建函数的C语言实现实际运行速度往往比纯Python的for循环更快。4.3 验证方法自己造数据用对拍确认正确性写完代码最怕什么怕它过了样例但过不了隐藏测试。这里我推荐一个通用技巧对拍。对拍就是写一个暴力解法和一个优化解法让它们都跑同一批随机输入然后逐行对比输出。拿这道题来说你可以写一个最简单的暴力程序比如用冒泡排序去重再用桶排序版本然后自己写脚本生成1000组随机的N和数字对比两个程序的输出是否完全一致。如果一致说明桶排序版本的逻辑没有偏差如果不一致立刻就知道是哪一行出了问题。这个方法适用于几乎所有算法题尤其是比赛和笔试阶段。我自己刷题时每道AC的题都会顺手写个对拍脚本用来反复验证边界情况比如N0、所有数字相同、数字包括1和1000的极端值等等。5. 笔试常踩的坑和我总结的检查清单5.1 输入格式与读取方式这道题输入只有两行第一行是N第二行是N个数。最简单也最稳的方式是循环读入所有整数不要假设它们一定在同一行。有些机试系统会把第二行的数字分散到多行如果你只按行读取并调用getline再解析就可能会漏数据。更稳妥的读法是用scanf(%d)或sys.stdin.read().split()它们会忽略换行符和空格自动把连续的数字流拆成一个一个整数。这个经验对很多“看起来很简单”的输入题目都通用。5.2 输出格式的陷阱空格、换行、多余符号很多人在输出格式上栽跟头。题目要求从小到大输出数字之间用一个空格隔开末尾一般没有多余空格。有的OJ严格逐字符比对末尾多了空格也算格式错误Presentation Error。我的做法是用一个first布尔变量控制空格第一个数字前不打印空格之后每个数字前打印一个空格这样最后一个数字后面就绝对不会出现多余空格了。Python里则可以用 .join(...)天然规避这个问题。另一个细节是输出完后一定要换行printf(\n)。有些程序最后一行没换行在肉眼看来没问题但在严格的判题系统里可能被判为Wrong Answer尽管逻辑完全正确。这种分失得真的冤。5.3 我自己的检查清单适用于所有去重排序题我给自己总结了一份快速自检清单写完代码后在脑子里过一遍能砍掉八成以上低级错误数组/列表大小是否合法会不会出现下标越界尤其是最大值等于边界的情况。去重逻辑是依赖容器特性还是手动比较手动比较是否覆盖了相邻元素相同和不相邻元素相同两种情况。输出时数字之间分隔符是否正确末尾有没有多余空格或缺失换行时间复杂度是否在题目限制内最坏情况是多少会不会超时多组输入时每一轮循环的数据结构是否都正确重置了比如flag数组有没有每轮清零这份清单不是只针对这道题它几乎能迁移到所有初级算法题上。每次提交前花30秒过一遍收益远大于代价。6. 从“明明的随机数”到真实业务场景的联想刷题刷到一定程度我会忍不住想这些题到底在模拟什么真实问题把“明明的随机数”放到工程语境里你会发现它其实无处不在。比如日志系统收集了用户行为ID要去重后按时间顺序输出比如爬虫抓回来一大批URL需要去重再按域名排序去重再比如电商平台要统计今天的打卡用户ID去重后按用户编号升序导出名单。所有这些场景都可以抽象成一句话一批数据去重按要求排序。从这个角度来看桶排序虽然在这道题里是最优解但它的局限性也很明显当数字范围非常稀疏且巨大时开一个大数组会浪费大量内存。这时候就该换用排序去重或者布隆过滤器这类更工程化的手段。有一瞬间你会突然明白面试官并不是真的想让你证明自己会写循环输出而是想看看你在去重和排序这一对基本需求面前有没有形成自己的方法论。我自己在做数据清洗时也经常用到类似的思想。比如有一份几百万行的CSV里面某个字段是用户ID我想知道有多少不同的ID且要按ID排列。写SQL自然是SELECT DISTINCT user_id ORDER BY user_id但如果你在内存里做思路就和这道题一模一样要么开哈希集合要么排序后去重要么用位图。所以你看一道看似简单的算法题沉淀下来的其实是通用的处理套路。7. 我在实际刷题中的几点体会以及这道题的扩展思考最后想分享一些个人化的经验不一定在题解里能看到。第一不要因为题简单就跳过动手编码的环节。我见过太多人看题解觉得“这题我会”就直接划走结果到机试现场写得磕磕巴巴。算法能力本质上是一种肌肉记忆哪怕再简单的题也值得你闭卷手写一遍然后想想有没有更优的写法。第二尽量用多种解法重刷同一道题。今天用桶排序写一遍明天用set写一遍后天试试手写快速排序加unique。每多一种解法你对这个题目的理解就深一层。特别是当你把不同解法的时间复杂度对比着看时会慢慢建立一种“复杂度直觉”这在后续刷难题时非常有用。第三这道题可以考虑做一个小扩展如果数字范围从1到1000变成1到10⁹但N仍然只有100你要怎么处理我的答案是改用set或排序去重因为桶排序无法直接开10⁹大小的数组。如果你能在脑子里快速想到这个替代方案说明你对这道题的理解已经不是“背答案”了而是真的理解了它背后的算法权衡。第四做题时注意命名规范。很多机试阅卷系统不会因为你变量名写的烂就扣分但在面试现场白板编程时面试官会观察你的代码风格。写flag、n、x没有问题但如果写a1、b2这种不知所云的变量名即使逻辑正确也会留下很差的印象。从小学会写好代码的第一直觉是刷题带给你除AC之外的额外红利。这道题确实不难但它像一面镜子能照出你基础是否扎实、习惯是否良好、思维是否能快速从一个方案切换到另一个方案。认真对待这道“送分题”把它吃透你会在后续刷题路上少走不少弯路。如果它后面还有类似的简单题我的建议是每一道都按“阅读题干—描述思路—多方案对比—手写代码—对拍验证—思考数据范围变化”的标准流程走一遍这种训练方式比稀里糊涂刷一百道题更有价值。