企业官网建设流程全解析

最近在整理大厂面试算法真题回忆，写到第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 的TreeSet<Integer>。这个集合底层是红黑树，插入时会自动按大小排序，同时自动忽略重复元素。于是“去重”和“排序”两个需求直接用一种数据结构就全部解决了。

参考代码：

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(); TreeSet<Integer> 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(); HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++) { set.add(sc.nextInt()); } List<Integer> 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 几种常见方案横向对比

为了在面试中快速组织答案，可以把几种方案放在一起对比：

这里的 M 表示去重后的元素个数。由于题目中 N 和数字范围都很小，实际上四种方案性能都能满足要求。但面试官问“最优解”时，布尔数组方案最接近 O(N) 时间复杂度，而且代码还最短，所以这是标准答案之一。

4.4 边界条件：N 为 0 或数值越界

如果 N 为 0，布尔数组方案的 for 循环不执行，输出阶段也不会打印任何内容，行为正确。但要注意，如果用seen[x] = true且没有范围判断，一旦输入出现 1001 或者 0，seen[1001]会直接数组越界。所以建议大家保留范围判断。

另外，这个方案的“排序”其实依赖固定扫 1000 次。如果面试官把数字范围改成 1 到 10 亿，再开boolean[10亿]就不现实了。这时候需要回到通用方案，先排序或使用 HashSet 再排序。你可以在回答里主动说“这个方案成立的核心是数值范围足够小”，这样会显得不是背题，而是真的理解问题。

5. 手写快排 + 去重：如果面试官不让你用 API

5.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 一样会自动跳过空白。如果用的是scanf，scanf("%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。逼自己多答一轮追问，比如“如果现在不允许用额外空间”“如果数字范围很大”“如果不能调用排序函数”，每多回答一个变体，你对这道题的理解就深一层。面试挂掉往往不是因为难题不会，而是简单题暴露出知其然不知其所以然。能在一道随机数题上把排序、去重、复杂度、边界都聊透，面试官对你基础能力的信任感会明显不一样。