最近在整理大厂面试算法真题回忆写到第176篇正好就是这道被很多同学称呼为“送分题”的“明明的随机数”。题目本身确实不长明明生成 N 个 1 到 1000 之间的随机整数重复数字只保留一个再从小到大排序输出。但别急着高兴很多人在笔试环境里能快速用 TreeSet 或排序做出来一到面试官追问“为什么”“还能不能更快”“数组范围变了怎么办”就懵住了。这道题在 LeetCode 讨论区也经常被拿出来当热身题但大厂面试考它其实考的不是你能不能 AC而是你对“去重”和“排序”这两个基础动作到底理解到什么程度。它适合准备校招、社招基础轮以及想补算法基础的同学认真过一遍。下面我把这道题从题目解读、多解法、复杂度分析到机试输入输出陷阱、面试追问应对完整拆开聊一遍。1. 先读懂题意这道“送分题”到底在问什么1.1 原题描述和输入格式为了便于后面展开先把题意用自己的话说清楚。输入第一行是一个整数 N表示明明生成了 N 个随机整数N 不超过 1000。第二行是 N 个用空格隔开的整数数字范围在 1 到 1000 之间中间可能出现重复。要求程序去掉其中重复的数字再把剩下的数字从小到大排序最后每个数字单独占一行输出。举个例子假设输入10 20 40 32 67 40 20 89 300 400 15这里 20 出现了两次40 出现了两次其余数字各出现一次。去重之后剩下20 40 32 67 89 300 400 15再排序输出为15 20 32 40 67 89 300 400很多人容易忽略的是“每次输出一个数字单独一行”。如果按照空格分隔输出部分测试程序会直接判错。后面会专门说输出格式的坑。1.2 面试里的版本差异并不是只有一套输入输出在牛客和不少机试平台上“明明的随机数”是非常经典的入门题。但在 LeetCode 讨论区或者面试官口头给题的时候形式经常会被改写。有的面试官会要求你写一个函数输入一个整型数组返回去重排序后的数组有的会要求你在控制台程序里读取标准输入还有的会追加限制条件比如“不能使用额外空间”“不允许调用现成的排序 API”“如果数字范围变成 10^9 怎么办”。这种情况下如果你只背了刷题网站上最常见的解法很可能就会卡壳。所以刷这道题的时候千万别只记一套答案。要把每种解法背后的思路吃透知道“为什么这样做”“在什么条件下选择哪个方案”这样不管面试官怎么变形你都能接得住。1.3 这道题承担着怎样的筛选作用别看这道题代码量很短大厂基础轮非常喜欢用它来快速判断候选人的编码素养。第一它考验代码是否干净。同样是完成去重排序有人两三行写得清清楚楚有人写完循环自己都数不清层数。第二它考验边界意识。N 有可能为 0输入数字可能在边界值 1 和 1000数组下标很容易越界。第三它考验复杂度分析。面试官问“有没有比 O(N log N) 更快的方案”你能不能想到利用数值范围做计数排序。第四它考验语言底层掌握程度。TreeSet 底层是什么Arrays.sort 对基本类型用的是什么排序这些追问都能从一个简单题延伸开去。所以把这道题当作一个“算法面试微缩模型”来准备性价比非常高。2. 万能保底法先排序再相邻去重2.1 核心思路让重复的数据变成邻居去重最朴素的想法就是“相同元素只保留一个”。如果不排序相同元素散落在数组各个位置要找全一遍得反复遍历复杂度很难看。但排序之后相同元素一定会靠在一起就像一堆混在一起的球按颜色分类后同色球都排到了一起。这时候只需要从左到右扫一遍遇到和上一个不一样的才保留就能完成去重。这个思路的优点是通用性强。哪怕题目里数字范围变成 1 到 10 亿这个方案依然成立只需要一个排序算法和一次线性扫描就能解决。缺点是排序本身有 O(N log N) 的时间复杂度。如果 N 很小比如不超过 1000这个复杂度完全够用也是我在机试环境里最先想到的保底方案。2.2 Java 参考实现与逐行解读如果是在 Java 环境里最直接的方式是读入数组后用Arrays.sort排序再用一个整数指针len做原地去重。参考代码import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } Arrays.sort(arr); int len 0; for (int i 0; i n; i) { if (i 0 || arr[i] ! arr[i - 1]) { arr[len] arr[i]; } } for (int i 0; i len; i) { System.out.println(arr[i]); } } }这里的关键点是len同时承担了“新数组写入位置”和“去重后数组长度”两个职责。每遇到一个不等于前一个元素的数字就把它覆盖到arr[len]然后len加一。因为在排序后的数组里重复元素只会在第一次出现时被保留后续相同的都会被跳过。如果面试官要求不能修改原数组那就不要用原地覆盖而是新建一个同样大小的result数组把去重后的结果放进去。思路一致只是多花 O(N) 的额外空间。2.3 复杂度是多少什么时候选它这个方案的时间复杂度由排序主导是 O(N log N)去重扫描是 O(N)所以整体是 O(N log N)。空间复杂度取决于去重方式原地覆盖是 O(1)如果使用额外结果数组则是 O(N)。在 N 1000 的范围内这个方案几乎不可能超时代码也容易写对所以是我的保底选择。但要是面试官追问“能不能做到 O(N) 时间”就需要往下看计数排序的思路了。另外还要注意一点Java 的Arrays.sort(int[])底层是双基准快速排序不是稳定排序。但对于整数去重排序来说稳定性没有意义因为重复数字本身是无法区分先后次序的。你可以在面试中主动提到这一点会显得对排序原理更清楚。3. 用集合当帮手TreeSet 与 HashSet 的选择题3.1 TreeSet一把梭解决“去重排序”在笔试时间紧张时很多人的首选是 Java 的TreeSetInteger。这个集合底层是红黑树插入时会自动按大小排序同时自动忽略重复元素。于是“去重”和“排序”两个需求直接用一种数据结构就全部解决了。参考代码import java.util.Scanner; import java.util.TreeSet; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); TreeSetInteger set new TreeSet(); for (int i 0; i n; i) { set.add(sc.nextInt()); } for (int num : set) { System.out.println(num); } } }写完这段代码我自己测过多次几乎不会有边界问题。即使 N 为 0循环不执行后面遍历空集合也不会报错。不过要清楚它的代价每次add都是一次红黑树插入复杂度 O(log M)M 是集合中不同元素的个数。整体时间复杂度 O(N log M)由于 M N 1000实际执行速度依然很快。3.2 HashSet 再排序更贴近多数语言习惯TreeSet虽然代码少但红黑树并不是所有语言默认都有。很多算法面试者更习惯先用HashSet去重再对结果排序。Java 的参考写法import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); HashSetInteger set new HashSet(); for (int i 0; i n; i) { set.add(sc.nextInt()); } ListInteger list new ArrayList(set); Collections.sort(list); for (int num : list) { System.out.println(num); } } }HashSet的add平均是 O(1)所以去重阶段更快。去重完成后集合是无序的必须显式排序。这种“先收集不重复元素再统一排序”的思路更接近工程常见写法也更容易扩展到数字范围很大的场景。如果面试官问“HashSet 和 TreeSet 怎么选”你可以说数据量小且要求代码简洁TreeSet 方便数据量较大且只想去重、最后统一排序HashSet 加外部排序通常更高效。TreeSet 的好处是集合本身时刻有序如果需要频繁获取当前最小值它更合适。3.3 面试官灵魂拷问内置排序还是手写排序这道题的隐藏考点之一是“你知不知道语言自带排序是怎么实现的”。有的同学一上来就用Collections.sort或Arrays.sort被追问“能不能不用库函数”时愣住了。我的建议是分两层回答。首先承认工程上应该用成熟的内置排序正确性好、效率高然后立刻补一句“如果改成手写我会用快速排序核心流程是选基准、分区、递归”。接着可以顺手写下快排。这样既展示工程判断力又展示基本功。不要小看这个追问。面试官不是真的想让你不用库函数而是想确认你知道排序背后在干什么。只知道“用 set 去重再转 list 排序”的学生和能解释 TreeSet 是红黑树、HashSet 是哈希表、Arrays.sort 对基本类型用双基准快排的学生在面试官心中的分量是完全不同的。4. 针对数据范围做优化布尔数组/位图计数4.1 为什么可以用非比较排序在常规印象里排序的时间复杂度下限是 O(N log N)因为比较排序至少要区分 N 个元素的不同排列。但这里有隐藏条件所有数字都在 1 到 1000 之间。这就让事情有了质变。打个比方要给 100 个人按出生月份排序不需要把每个人和其他人两两比较。准备 12 个月份的桶每个人属于哪个月的就放进哪个桶最后依次把桶里的内容倒出来自然就是有序的。这个过程完全绕开了“两两比较”所以复杂度可以做到 O(N 范围大小)也就是所谓的计数排序思路。这道题更简单因为重复数字只保留一个我甚至不需要记录每个数字出现了几次只需要一个布尔标记。数字 x 出现过就把seen[x]设为 true最后从 1 到 1000 遍历哪个下标为 true 就输出哪个。4.2 布尔数组实现与全代码Java 实现如下import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); boolean[] seen new boolean[1001]; for (int i 0; i n; i) { int x sc.nextInt(); if (x 1 x 1000) { seen[x] true; } } for (int i 1; i 1000; i) { if (seen[i]) { System.out.println(i); } } } }这里的boolean[1001]下标 0 不使用真正有意义的是seen[1]到seen[1000]正好对应题目的数字范围。输入读到数字 20就把seen[20]置为 true再读一个 20依然是 true重复自然被忽略。输出阶段从 1 扫到 1000扫到的顺序就是升序不需要再做排序。代码里加了一个if判断防止测试数据出现越界的情况。虽然题目保证范围但加上这个判断能让面试官觉得你边界意识很强。4.3 几种常见方案横向对比为了在面试中快速组织答案可以把几种方案放在一起对比方案时间复杂度空间复杂度代码量适用场景排序 相邻去重O(N log N)O(1)中数字范围大、通用TreeSetO(N log N)O(M)少数据量小、追求简洁HashSet 排序O(N M log M)O(M)中数据量大、需要去重再排序布尔数组计数O(N 1000)O(1001)少数字范围小且已知这里的 M 表示去重后的元素个数。由于题目中 N 和数字范围都很小实际上四种方案性能都能满足要求。但面试官问“最优解”时布尔数组方案最接近 O(N) 时间复杂度而且代码还最短所以这是标准答案之一。4.4 边界条件N 为 0 或数值越界如果 N 为 0布尔数组方案的 for 循环不执行输出阶段也不会打印任何内容行为正确。但要注意如果用seen[x] true且没有范围判断一旦输入出现 1001 或者 0seen[1001]会直接数组越界。所以建议大家保留范围判断。另外这个方案的“排序”其实依赖固定扫 1000 次。如果面试官把数字范围改成 1 到 10 亿再开boolean[10亿]就不现实了。这时候需要回到通用方案先排序或使用 HashSet 再排序。你可以在回答里主动说“这个方案成立的核心是数值范围足够小”这样会显得不是背题而是真的理解问题。5. 手写快排 去重如果面试官不让你用 API5.1 快速排序的循环不变式手写快速排序是面试里绕不开的基本功。哪怕这道题用布尔数组能一行搞定面试官也可能让你手写一个排序验证你代码能力。快排的核心思想是分治选一个基准元素通过交换让小于基准的值都集中到左边大于基准的值都集中到右边然后对左右两侧递归排序。实现时我用的是“双指针从两端向中间逼近”的写法个人觉得比单路扫描更容易写对尤其在包含大量重复元素时不容易退化。写递归前先要清楚循环不变式在每一轮循环开始前左指针左边到基准之间的元素都应当小于等于基准右指针右边到基准之间的元素都应当大于等于基准。最后两个指针交错时就可以递归处理左右两个子区间了。5.2 参考实现双路快排简洁版一个可以直接背下来的 Java 实现public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivot arr[left (right - left) / 2]; int i left; int j right; while (i j) { while (arr[i] pivot) { i; } while (arr[j] pivot) { j--; } if (i j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; i; j--; } } quickSort(arr, left, j); quickSort(arr, i, right); }代码里pivot选择中位数下标的写法是为了避免(left right) / 2在 left 和 right 都很大时可能溢出。虽然这题 N 只有 1000但好的习惯要养成。双路快排处理重复元素尤其稳因为当arr[i]等于 pivot 时也会通过交换被移到另一侧元素不会全部堆到一边递归树相对平衡。调用完整流程是读数组后先quickSort(arr, 0, n - 1)再写去重逻辑。5.3 排序后去重的两种写法手写快排完成之后去重有两种常见写法。第一种是原地覆盖和前面用Arrays.sort之后的逻辑完全一样int len 0; for (int i 0; i n; i) { if (i 0 || arr[i] ! arr[i - 1]) { arr[len] arr[i]; } }第二种是输出时跳过重复项不改原数组if (n 0) { System.out.println(arr[0]); for (int i 1; i n; i) { if (arr[i] ! arr[i - 1]) { System.out.println(arr[i]); } } }第二种写法适合面试官明确说“不能修改原数组但可以输出结果”的情况。注意先判断n 0否则访问arr[0]会越界。5.4 手写排序时的常见失误清单手写快排的失误点很固定我把踩过的坑整理一下。递归出口写错位。如果写成if (left right)当 left 大于 right 时不会直接返回可能进入无限递归。必须写成if (left right)。忘记更新指针。交换完成后如果忘了i和j--可能出现arr[i] pivot为 false 的情况但指针不再移动导致死循环。选固定arr[left]做基准。当数组已经有序时固定选最左端作为基准会导致递归极不平衡最坏时间复杂度退化成 O(N^2)。所以尽量选中间下标或者随机下标。交换条件写成i j而不是i j。如果 i 和 j 相等且该元素恰好等于 pivot交换后两个指针不会跨过彼此最后递归区间可能重叠结果错误。去重时对arr[i 1]越界。很多人喜欢写arr[i] arr[i 1]判断但 i 的终止条件没控制好i 1 就会访问到数组末尾之外。建议统一用当前元素和上一个元素比较控制循环从 1 开始。6. 机试/笔试的输入输出陷阱别让代码输在 IO 上6.1 多行读入的正确姿势很多机试场景里第一行是 N第二行是 N 个数字但测试数据不一定老老实实按照这个格式排布。有时候第二行只有几十个数字剩下的数字被折到第三行、第四行尤其是随机生成的测试用例容易这样。Java 用Scanner的时候sc.nextInt()会自动跳过任何空白字符包括空格和换行所以理论上不存在“读不满”的问题。但如果你图省事用BufferedReader.readLine()一次性读一整行就可能只读到部分数字。更稳健的做法是先用Scanner或者用BufferedReader把所有输入拼起来再统一切分BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb new StringBuilder(); String line; while ((line br.readLine()) ! null) { sb.append(line).append( ); } String[] parts sb.toString().trim().split(\\s);这样无论数字被分成多少行都能正确读取。不过要注意parts的第一个元素是 N需要解析后决定往后取多少个数。6.2 Python 的列表推导与分片Python 写法中最省心的是一口气读取所有整数然后用切片取出 N 个数import sys data list(map(int, sys.stdin.read().split())) if not data: exit() n data[0] nums data[1:1 n] for v in sorted(set(nums)): print(v)sys.stdin.read()会把标准输入里的所有内容一次性读进来split()按空白字符切分所以同样不害怕数字跨行。set(nums)负责去重sorted负责升序排列。最后循环逐行打印。这段代码里我用了data[1:1 n]是为了严格遵守题目“第二行只有 N 个数字”的语义。如果数据本身只有 N 个数字用data[1:]也没有问题。但切片写法更严谨能避免意外多读。6.3 C 的 cin/scanf 细节C 里最简单的写法是直接cin x因为它和 Java 的 Scanner 一样会自动跳过空白。如果用的是scanfscanf(%d, x)同样会自动跳过空格和换行不需要手动处理。完整参考#include bits/stdc.h using namespace std; int main() { int n; cin n; bool seen[1001] {false}; for (int i 0; i n; i) { int x; cin x; if (x 1 x 1000) { seen[x] true; } } for (int i 1; i 1000; i) { if (seen[i]) { cout i \n; } } return 0; }这里bool seen[1001]是局部变量但只占 1001 个字节栈上放得下。如果在其他题目里数组长度达到百万级局部变量可能栈溢出需要放到全局区或者用动态数组。这个细节也可以顺便跟面试官聊一下。6.4 输出格式换行的耐心“明明的随机数”输出要求是每个整数单独一行所以打印时必须用println或\n。如果图省事用空格分隔会直接判错。如果题目改成“结果之间用空格分隔”输出时需要注意行尾不要留多余空格。一种好方法是把结果收集到StringBuilder每加入一个数字之前判断当前长度是否大于 0大于 0 就先追加一个空格。这样最后一个数字后面不会有多余空格代码也简洁。这类输入输出细节看似不起眼但在真实机试环境中代码逻辑全对却因为多了一个空格被判定错误的情况太多了。7. 面试追问地图从“会做”到“讲明白”7.1 高频追问清单我把围绕这道题我实际遇到过的追问整理成下面几类大家可以照着自查。这道题有哪几种解法每种复杂度是多少为什么数字范围限制在 1 到 1000 时可以用布尔数组如果数字范围变成 1 到 10^9布尔数组方案还成立吗如果 N 变成 10^7但数字范围还是 1 到 1000选哪个方案最优如果要求不使用额外空间怎么处理如果要求不能修改原数组怎么处理TreeSet 的底层是什么插入和删除复杂度是多少HashSet 和 TreeSet 在什么场景下选哪个手写快速排序时如何处理大量重复元素排序后去重输出时如何避免最后一个元素多一个分隔符这些问题全部都可以从这道入门题延伸出来。每一问都没有必须背的固定答案但你需要把思路顺下来。7.2 一套有话可说的回答模板我建议的回答结构是“先通用再最优最后退化”。首先说“我看到题目第一反应是排序后去重。用系统排序把数组排好然后扫描一遍遇到和前一个不一样的元素就保留。时间复杂度 O(N log N)空间复杂度可以做到 O(1)。”然后主动补充“但这道题有个很特殊的前提所有数字都在 1 到 1000 之间。这让我想到计数排序的思路用一个长度为 1001 的布尔数组读到一个数字就把对应下标置为 true最后从 1 扫到 1000 输出。这样时间复杂度是 O(N 1000)空间复杂度是 O(1000)也就是常数级别的额外空间。”最后加上一句“如果数字范围变大比如到 10 亿布尔数组就不合适了我会回到排序后去重或者用 HashSet 去重后再统一排序。”这套回答的好处是先给一个肯定正确的通用解再展示你能利用题目条件做优化最后说明边界变化后的处理思路。面试官听完基本能判断你确实理解了算法而不是背答案。7.3 现场回答节奏参考之前有位同学在模拟面试时一上来就写了 TreeSet代码很短当时也很得意。结果面试官问了一句“TreeSet 底层是什么插入复杂度多少”他回答“是树log n 吧”勉强过关。又问“能 O(N) 吗”他在纸上画了很久才想到布尔数组。事后复盘他的问题是没有先分析数据范围。如果换成我来回答我会先读题时快速判断“N 最多 1000数值范围是 1 到 1000。”有了这句话铺垫后面引出布尔数组就非常自然。面试官问“还有没有更好方案”时你甚至可以主动说“因为数字范围很小我倾向于用计数数组虽然这个数量级下排序也不慢但布尔数组代码更简洁时间复杂度也更理想。”这种“主动展示思考过程”的节奏比等面试官追问要加分很多。你可以把面试想象成一场技术讨论而不是一次考试。边写代码边小声解释自己在做什么、为什么这么做对方也能更快理解你的水平。“明明的随机数”这样的题我实际刷过很多遍每次重新写都会有点新收获。第一遍用最顺手的集合写好第二遍手写快排去重第三遍用布尔数组压到极限同时把输入改成大数据量版本再想一遍。练习简单题时把数据范围换着玩比如把 1000 改成 10 亿解法马上变这个过程能真正帮你理解算法选择的权衡。最后再分享一个小技巧遇到这类“一看就会”的题目别满足于 AC。逼自己多答一轮追问比如“如果现在不允许用额外空间”“如果数字范围很大”“如果不能调用排序函数”每多回答一个变体你对这道题的理解就深一层。面试挂掉往往不是因为难题不会而是简单题暴露出知其然不知其所以然。能在一道随机数题上把排序、去重、复杂度、边界都聊透面试官对你基础能力的信任感会明显不一样。