企业官网建设流程全解析

又到了我翻大厂面试算法真题回忆系列的时候，第176期轮到一道看起来有点“过于亲民”的题——明明的随机数。说句实话，第一次看到这道题的人，十个里有八个会觉得：就这？生成随机数、去重、排序，三分钟写完的入门题。但后来我在某大厂的模拟面试里，因为这道题被面试官从布尔数组问到哈希表，再问到流式数据，才发现自己漏掉了整条隐藏的知识链。今天就从题目分析开始，把三种解法、四种追问方式和刷题套路完整拆给大家。适合刚开始刷题的同学，也适合面试前想查漏补缺的朋友。

1. 题目到底在考什么：别被“简单题”骗了

1.1 原题描述与输入输出格式

题目的原始场景是这样的：明明想在学校里请一些同学做调查，他让计算机随机生成了 N 个整数，整数的取值范围是 1 到 1000。因为随机数可能重复，而重复的数代表的是同一位同学，所以明明需要先去掉重复的整数，再把这些整数从小到大排序，最后按顺序去找同学。

放到算法题里，输入有两行：第一行是一个整数 N，表示随机数的个数；第二行是 N 个用空格隔开的整数。要求的输出也有两行：第一行是去重排序后剩下多少个不同的数，第二行是这些数从小到大排列的结果。

我看到这个输入输出格式的时候，第一反应是：真的没有隐藏部分吗？确实没有。但正因为题目表面干净，才给了面试官充分的空间往深了挖。N 的范围题目里通常会给出，常见约束是 N≤100，数值上限同样是 1000。这两个数字不是白给的，它们直接决定了最优解法走哪条路。

1.2 第一眼的直觉解法与它为什么不够

绝大多数人看到“去重+排序”，第一反应就是先排序，再跳过重复项。因为排序之后，相同的数字一定会相邻，只要在遍历时判断当前数字和上一个是否相同，不相同就加入结果，时间复杂度是排序的 O(N log N)。这个思路没有任何错误，我也更愿意把它称为“及格线解法”。

但在面试场景里，只给出及格线解法往往意味着追问即将到来。面试官不会因为你写出了一个能过的解法就满意，他会接着问：有没有更优的做法？这个 N 的范围合理吗？如果把 N 变成 10 万，你的排序还能打吗？为什么题目限定数值在 1 到 1000？

这就是常见刷题路径的陷阱：很多人以为能 AC 就是终点，实际上在面试中，AC 只是入场券，真正决定印象分的是你能否顺着数据范围说出更合适的方案。

1.3 面试中真正要考察的三个点

第一，是对数据范围敏感度的考察。题目告诉你数值范围是 1 到 1000，就意味着你可以用固定大小的数组去当“标记位”，这是典型的“借助值域压缩信息”思路。很多候选人看不到这一点，直接排序交了，也不是错，但缺少了一点让面试官眼前一亮的敏感度。

第二，是空间换时间这种权衡能力的考察。哈希集合去重很方便，但它会引入额外空间。换到桶数组呢？同样需要额外空间，但能把时间复杂度降到线性。你需要根据约束条件判断什么样的空间代价是值得的。

第三，是输入处理和边界条件的细心程度。N 可能为 0 吗？第二行的数据会不会换行？输出第一行的个数和第二行的列表，顺序能不能反？这些细节恰恰是线上代码和面试手写代码拉开差距的地方。我见过很多同学代码逻辑完全正确，却在输出格式上被扣分，非常可惜。

2. 解法一：排序后去重——最稳妥的及格线

2.1 思路讲解：让重复元素住隔壁

先排序，再利用“排序后重复元素必然相邻”这个性质去重。这句话是整道题解法一的核心。

举个例子，输入是 2 5 2 1 1 4。排序后变成 1 1 2 2 4 5。遍历时，第一个数字 1 直接加入结果；第二个数字 1 和当前结果最后一个元素相同，跳过；遇到 2 时，和上一个 2 不同，加入结果。最终得到 1 2 4 5。

这个思路的好处是，你不用额外记住“这个数字出现过没有”，因为排序已经把所有相同的元素挤到一起了。代价是排序本身的消耗。在数据量不大时，这个消耗完全无所谓，代码也最好写，不容易出错。

2.2 代码实现：Python与C++对照

Python 版本：

n = int(input()) nums = list(map(int, input().split())) nums.sort() res = [] for x in nums: if not res or x != res[-1]: res.append(x) print(len(res)) print(' '.join(map(str, res)))

这里res[-1]是结果列表的最后一个元素。由于列表有序，只要当前数字和最后一个不一样，就说明它没有出现过。如果你担心input().split()可能因为换行读不全，可以用循环读取直到收集满 N 个数字，后面在第五部分我会专门讲这个坑。

C++ 版本：

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } sort(a.begin(), a.end()); vector<int> res; for (int x : a) { if (res.empty() || x != res.back()) { res.push_back(x); } } cout << res.size() << '\n'; for (int i = 0; i < (int)res.size(); ++i) { if (i) cout << ' '; cout << res[i]; } cout << '\n'; return 0; }

C++ 里也可以用标准库的unique函数，它会把重复元素移动到末尾并返回新的结尾迭代器，配合erase使用能更简洁：

sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end());

不管是手写循环还是用标准库，核心逻辑都是一样的：先让重复元素紧挨着，再忽略它们。

2.3 复杂度分析与面试陈述要点

时间复杂度主要由排序贡献，O(N log N)。遍历数组那部分只有 O(N)，会被排序吞掉。空间复杂度取决于你是否新开了res数组，如果新开了，就是 O(N)；如果你选择用原数组原地修改，比如用双指针把不重复的元素覆盖到前面，空间可以做到 O(1)（不计入排序的递归栈空间）。

在面试中，你要这么陈述：“先整体排序，然后一遍扫描去重，时间复杂度 O(N log N)，空间尽量控制在 O(1) 到 O(N) 之间。”如果你能顺手提一句“如果允许原地覆盖，我可以不额外创建结果数组”，面试官会认为你关注内存占用，这是加分项。

但注意，这道题的值域只有 1000，排序其实引入了一个并不必要的 O(log N) 因子。这时候面试官大概率会接一句：“能不能不要排序，也完成输出？”这句话就是通往解法三的台阶。

3. 解法二：哈希集合去重——用空间换时间

3.1 思路讲解：先甩掉重复，再排序

既然要去重，最自然的工具是哈希集合。把每个数字丢进Set，集合自动保证不重复。但哈希集合不保证有序，所以去重完成后还要再做一次排序。

这个思路比排序后去重好在哪？如果输入中重复元素很多，排序法仍然要对所有 N 个元素排序，而哈希集合法只需要对去重后的 M 个元素排序。最坏情况下不重复元素 M 接近 N，优势不大；但如果重复率很高，集合法省下的排序成本就很明显。

当然，在题目原本 N≤100 的约束下，这种优势几乎可以忽略。它更重要的价值是展示你知道“空间换时间”这个基本策略，以及你对容器特性的理解。

3.2 代码实现：Python与Java对照

Python 版本非常简短：

n = int(input()) nums = list(map(int, input().split())) res = sorted(set(nums)) print(len(res)) print(' '.join(map(str, res)))

set(nums)去重，sorted(...)排序，一行搞定。很多刷题同学喜欢这种写法，因为它少了很多模板代码。但面试手写时我建议你拆开写，并主动解释每一步的复杂度，别让面试官觉得你只会调包。

Java 版本，用HashSet去重，再转成List排序：

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Set<Integer> set = new HashSet<>(); for (int i = 0; i < n; i++) { set.add(sc.nextInt()); } List<Integer> list = new ArrayList<>(set); Collections.sort(list); System.out.println(list.size()); for (int i = 0; i < list.size(); i++) { if (i > 0) System.out.print(' '); System.out.print(list.get(i)); } System.out.println(); } }

Java 还有一种更省事的写法是用TreeSet，它在插入时就维护了有序性，去重和排序一步到位。但底层是红黑树，插入操作是 O(log M)，整体复杂度会变成 O(N log M)，反而不如HashSet + Collections.sort的 O(N + M log M) 直观。所以面试中别为了少写一行代码就在复杂度上吃亏。

3.3 面试追问：Set去重后排序为什么不是最优？

如果候选人写了这套解法，面试官通常会问：“你用了额外空间，但时间复杂度真的比排序法更优吗？”

你要这样分析：设输入规模为 N，去重后剩下 M 个数字。哈希集合的插入过程是 O(N)，排序过程是 O(M log M)，整体是 O(N + M log M)。如果 M 很小，这当然很快；但如果 M 接近 N，它和直接排序差不多，甚至因为哈希表的内存布局问题，实际运行还慢一点。

更关键的追问是：“题目数值范围是 1 到 1000，你有没有想过用一个大小为 1001 的数组替代哈希集合？”这句话其实就是提示你：哈希集合确实能处理任意值域，但正因为它的通用性，它在本题这种“值域已知且很小”的场景下反而绕了远路。你不需要对任意值域做哈希，只需要把数字本身当作下标，就能同时完成去重和排序。

从这道题开始，面试话题就会被引到第三类解法上。

4. 解法三：桶排序/计数排序——利用值域限制打出“最优解”

4.1 核心思想：1到1000，不是给你看看的

题目明确告诉你随机数范围是 1 到 1000，这其实是一个巨大的提示。你可以直接开一个大小为 1001 的布尔数组（下标 0 不用，下标 1 到 1000 对应每个可能出现的数字），每遇到一个数字 x，就把seen[x]标记为true。

一遍输入处理完，重复的数字自然被标记位“合并”了。最后从小到大遍历这个布尔数组，遇到为true的下标就输出下标本身。因为遍历顺序本身就是升序，排序也自动完成了。

这就叫桶排序思想的简化版，或者叫计数排序的“存在性版本”。它把去重和排序合并成了一件事，不需要任何比较操作，所以复杂度能达到线性。

4.2 代码实现：布尔数组版本

C++ 实现：

#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; seen[x] = true; } int cnt = 0; for (int i = 1; i <= 1000; ++i) { if (seen[i]) cnt++; } cout << cnt << '\n'; for (int i = 1; i <= 1000; ++i) { if (seen[i]) cout << i << ' '; } cout << '\n'; return 0; }

注意 C++ 里bool seen[1001] = {false};会把整个数组初始化为 false，这是局部数组初始化的一种安全写法。如果你不初始化就定义局部数组，里面可能是随机残留值，调试起来非常痛苦。

Python 实现：

n = int(input()) seen = [False] * 1001 for x in map(int, input().split()): seen[x] = True res = [i for i in range(1, 1001) if seen[i]] print(len(res)) print(' '.join(map(str, res)))

这里把结果列表用列表推导式一次性生成，代码很清爽。如果你想省内存，也可以不生成res，而是第一次遍历计数，第二次遍历输出，但那样代码会略长。面试时我更推荐先生成结果列表，因为它便于检查中间状态，也方便后续处理。

4.3 复杂度说明：O(N+M)为什么在本题更好

处理输入的那一层循环要遍历 N 个数字，时间复杂度 O(N)。输出前要遍历整个值域范围，也就是从 1 扫到 1000，时间复杂度 O(M)，这里 M=1000 是值域大小，不是去重后的个数。所以总时间复杂度是 O(N+M)。

因为 M 是固定常数（1000），我们可以说它近似 O(N)。这比排序法的 O(N log N) 要漂亮得多。空间复杂度是 O(M)，布尔数组大小固定，不随 N 增长，所以也算稳定。

面试时不要只说复杂度公式，要强调“在本题值域固定的前提下，M 是常数，因此这套解法是线性时间”。如果你只丢出 O(N+M)，面试官可能一时反应不过来；你把常数项解释清楚，他才觉得你真的吃透了。

4.4 变种讨论：如果值域不是1000而是10^9怎么办

如果取值范围变成 1 到 10^9，布尔数组方案直接宣告破产，因为你不可能开一个长度 10 亿的数组。这时候你需要回到排序法或哈希集合法。

这里有个很好的方法论：看到“有限值域”四个字，优先考虑桶类做法；看到“值域极大但输入量有限”，优先考虑哈希表压缩信息；看到“数据量极大且无法全部装入内存”，就必须考虑外部排序或分治思想。

我在面试的时候会这样回答：“如果值域变成 10^9，我会分析 N 的量级。N 如果只有 10^5，直接用哈希集合去重后排序；如果 N 也很大，那么排序法更稳妥，因为它的空间复杂度可以做得更低。”这个回答展示了你会根据约束动态选择算法，而不是只会背模板。

5. 面试现场还原：一场由“明明”引发的连环追问

5.1 追踪一：N变成10^5，桶排序还成立吗

面试官从你的桶排序解法继续往前推：“如果现在 N 变成 10 万，甚至 100 万，值域还是 1 到 1000，你怎么选？”

这个问题的答案是：桶排序依然成立。因为它的复杂度是 O(N+M)，N 变大时仍然是线性增长，M 固定是 1000，没有理由换掉。你只需要继续用布尔数组处理即可，内存占用依旧是 1001 个布尔值，非常舒服。

但如果 N 变得非常大，比如 10^10，输入都没法一次性读入内存，这时候就要考虑分批处理。不过面试通常不会在内存模型上追到这种深度，你能说出“N 增大不会影响值域固定方案的内存，只是处理时间线性增加”就已经合格。

5.2 追踪二：排序稳定性与去重的边界

“如果题目要求保持输入顺序不变，只输出第一次出现的数字，再去重，你怎么办？”这是排序稳定性的经典追问。

这种情况下不能直接改桶排序，因为桶排序天然按值域输出，顺序一定变了。你需要用哈希集合来判重，同时按输入顺序遍历，遇到没见过的数字就加入结果并标记。这种场景下，哈希集合的价值就体现出来了。你可以对比一下：去重不一定需要排序，有时候顺序约束比排序约束更优先。

5.3 追踪三：输入不是整数而是浮点数怎么办

如果数字变成浮点数，桶数组就不能直接用了，因为浮点数的值域难以预先枚举。你只能走排序法，或者用哈希集合，但浮点数的相等判断需要小心。

“1.0”和“1”在某些语言中视为不同，但在题目语境下可能表示同一个数。更麻烦的是浮点运算精度，两个看似相同的结果可能是 0.9999999 和 1.0000001。你需要用“差值绝对值小于 eps”来判断相等，而不是直接比较==。这是一个非常细节但很讨面试官喜欢的回答点。

5.4 追踪四：流式数据到达，如何实时维护结果

“如果数字是一个接一个到达的，而不是一次性给你整个数组，你要怎么实时维护一个有序去重集合？”这个问题把离线算法变成在线算法。

最直接的方案是用平衡树，例如 Java 的TreeSet或 C++ 的set。每次插入一个数，如果集合中已有则忽略；如果没有就插入，且集合始终保持有序。单次插入 O(log M)，总复杂度 O(N log M)。这个解法在这个场景下反而是最优选择，因为你不能预先看完整数据，也无法依赖固定值域做全局桶。

如果你能在面试中说出“在线场景下，平衡树是首选”，面试官会认为你对数据结构的选择不是停留在刷题层面，而是有真实工程设计思维。

5.5 我踩过的坑：空输入、换行和输出格式

这道题我踩过三个特别经典的坑，写出来供大家避雷。

第一个坑是N=0。有些版本题目允许 N 为 0，如果输入为空数组，input().split()会拿到一个空列表，排序后结果为空。你在输出第二行时如果不加判断，可能会多输出一个换行，或者调用res[0]直接越界。一定要在代码开头想好空输入时的输出。

第二个坑是“第二行数据可能被折成多行”。OJ 的输入描述是“第二行有 N 个整数”，但真实测试数据有时会因为语法糖、换行符等原因，把数字分散到两行甚至更多行。很多同学只input().split()一次，导致读到的数字不够 N 个，程序直接报错。保险做法是写一个读取函数，循环收集直到拼够 N 个数字。

第三个坑是输出格式。题目要求第一行输出个数，第二行输出所有数字。有人只输出了第二行，有人把数字用逗号分隔，有人最后多了一个空格。虽然部分 OJ 会忽略行尾空格，但严格判题器会把你卡死。我的原则是：第一，个数单独一行；第二，数字之间用单个空格分隔；第三，最后最好加换行，但不要在行尾留多余空格。

6. 刷题方法论：从“明明的随机数”提炼出的套路

6.1 同类题快速识别：去重排序家族的指纹

“明明的随机数”其实是一类题的典型缩影，这类题有一个共同的指纹：看到“去掉重复”“去重”“统计不同元素”“排序后输出”这些字眼，你就要立刻在脑子里列出三条路线：排序去重、哈希集合去重、桶/计数排序。

举个例子，求两个有序数组的交集、合并两个无序数组并去重、统计一个数组中哪些数字出现次数超过阈值，这些题都共享同一个底层能力：你如何看待“出现一次”和“出现多次”。把这道题练透，再去做其他去重题会顺手很多。

6.2 三种解法选型对照表

我在刷题笔记里给这三种解法做了个表，每次遇到类似题直接对号入座：

这里的 M 有两种含义，我在第三列里用 M 表示值域大小，哈希集合里的 M 表示去重后元素个数，看表时要注意区分。

6.3 实操小测试：写代码验证三种解法的表现

光说不练不够。我建议你写一个随机数据生成器，把 N 放大到 10 万，然后分别用三种解法跑一遍，统计耗时和内存占用。

一个简单的 Python 测试脚本结构是这样的：

import time import random N = 100000 nums = [random.randint(1, 1000) for _ in range(N)] # 解法一：排序+去重 start = time.time() nums_sorted = sorted(nums) res1 = [] for x in nums_sorted: if not res1 or x != res1[-1]: res1.append(x) print("排序去重耗时:", time.time() - start) # 解法二：Set+排序 start = time.time() res2 = sorted(set(nums)) print("Set去重耗时:", time.time() - start) # 解法三：布尔数组 start = time.time() seen = [False] * 1001 for x in nums: seen[x] = True res3 = [i for i in range(1, 1001) if seen[i]] print("桶排序耗时:", time.time() - start)

我在自己机器上跑过，N 超过 10 万后，解法三的优势就非常明显，解法一和解法二会随着 N 增加逐渐拉开差距。你亲自测过之后，对复杂度的理解会比看十篇文章都深。

写在最后：这道题让我养成的习惯

有段时间我很迷信“标准答案”，碰到去重先排序，碰到排序就sort，很少去思考题目给出的值域范围是不是一个关键线索。后来在一次模拟面试里，面试官对着我的代码轻轻问了一句：“你能说一下输入数字的取值范围吗？”我当场愣住，因为那行set(nums)写得太顺手，完全忽略了自己正在处理一个只有 1000 个可选值的数据。

那次之后，我每次拿到算法题都强迫自己先干三件事：看数据范围、看输入规模、看输出要求。数据范围决定能不能用桶，输入规模决定排序能不能扛住，输出要求决定要不要额外处理格式。“明明的随机数”看起来是道入门题，但它其实是检验算法思维习惯的一面镜子。把这面镜子擦干净，后面很多题都会亮堂起来。