1. 项目概述

"明明的随机数"是华为OD机试中的一道经典题目，也是LeetCode上常见的算法练习题。这道题看似简单，却融合了数组处理、排序、去重等多个基础算法知识点，是检验程序员基本功的试金石。我在准备大厂面试时，曾反复练习这道题目，并总结出一套高效的解题思路。

题目描述：明明想在学校中请一些同学一起做问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成"去重"与"排序"的工作。

2. 核心需求解析

2.1 问题拆解

这道题目看似简单，实则包含三个核心需求：

1. 随机数生成：生成N个1-1000范围内的整数
2. 数据去重：去除数组中重复的元素
3. 结果排序：将去重后的数组按升序排列

2.2 输入输出分析

输入格式：

• 第一行输入随机数的个数N
• 接下来的N行每行输入一个随机数

输出格式：

• 去重排序后的结果，每行一个数字

示例： 输入： 10 20 40 32 67 40 20 89 300 400 15

输出： 15 20 32 40 67 89 300 400

3. 算法设计与实现

3.1 基础解法：使用集合去重

最直观的解法是使用集合(Set)的特性来自动去重，然后转为列表排序：

n = int(input())
nums = [int(input()) for _ in range(n)]
unique_nums = sorted(list(set(nums)))
for num in unique_nums:
    print(num)

时间复杂度分析：

• 集合去重：O(n)
• 排序：O(n log n)
• 总体：O(n log n)

空间复杂度：O(n)

注意：这种方法简洁但会改变原始输入顺序，在需要保持原始顺序去重时不适用。

3.2 进阶解法：手动去重+排序

对于面试场景，面试官可能希望看到手动实现的去重逻辑：

n = int(input())
nums = [int(input()) for _ in range(n)]

# 手动去重
unique_nums = []
seen = set()
for num in nums:
    if num not in seen:
        seen.add(num)
        unique_nums.append(num)

# 排序
unique_nums.sort()

# 输出
for num in unique_nums:
    print(num)

3.3 最优解法：利用计数排序思想

当数据范围已知且不大时（本题1-1000），可以使用计数排序的思想，兼具去重和排序：

n = int(input())
count = [0] * 1001  # 1-1000

for _ in range(n):
    num = int(input())
    count[num] = 1  # 标记存在

for i in range(1, 1001):
    if count[i]:
        print(i)

时间复杂度：O(n + 1000) → O(n) 空间复杂度：O(1001) → O(1)

这是最高效的解法，特别适合数据量大但范围有限的场景。

4. 大厂面试考点解析

4.1 常见考察点

这道题目虽然简单，但大厂面试官通常会从以下几个维度进行考察：

1. 基础编码能力：能否正确实现去重和排序
2. 算法复杂度分析：能否准确分析时间/空间复杂度
3. 边界条件处理：空输入、极值等情况
4. 代码风格：变量命名、注释、可读性
5. 优化思路：能否提出更优的解决方案

4.2 面试回答技巧

当面试官提出这道题时，建议采用以下回答策略：

1. 先确认题目要求和输入输出格式
2. 提出最直观的解法并分析复杂度
3. 逐步优化，讨论不同解法的优缺点
4. 最终给出最优解并解释选择理由
5. 讨论可能的边界情况和异常处理

例如： "对于这个问题，我首先想到用集合去重然后排序，时间复杂度是O(n log n)。考虑到数据范围已知且不大，可以采用计数排序的思想，这样时间复杂度可以优化到O(n)..."

5. 常见问题与优化

5.1 边界情况处理

实际编码中需要考虑以下边界情况：

• 输入N为0或负数
• 输入数字超出1-1000范围
• 大量重复数据的情况
• 输入数据量很大时的性能问题

改进后的健壮性代码：

n = int(input())
if n <= 0:
    exit()

count = [0] * 1001
for _ in range(n):
    try:
        num = int(input())
        if 1 <= num <= 1000:
            count[num] = 1
    except:
        continue

for i in range(1, 1001):
    if count[i]:
        print(i)

5.2 性能优化技巧

1. 输入优化：对于大规模数据，使用sys.stdin.readline()替代input()
2. 空间优化：如果内存紧张，可以使用位图代替数组
3. 并行处理：超大数据量时可考虑分块处理

位图实现示例：

import sys

n = int(sys.stdin.readline())
bitmap = 0  # 使用整数的位来表示数字是否存在

for _ in range(n):
    num = int(sys.stdin.readline())
    if 1 <= num <= 1000:
        bitmap |= 1 << num

for i in range(1, 1001):
    if bitmap & (1 << i):
        print(i)

6. 同类题目拓展

掌握这道题后，可以尝试解决以下类似题目：

1. LeetCode 26. 删除有序数组中的重复项
2. LeetCode 80. 删除有序数组中的重复项 II
3. LeetCode 215. 数组中的第K个最大元素
4. LeetCode 347. 前 K 个高频元素
5. LeetCode 451. 根据字符出现频率排序

这些题目都涉及数组处理、去重、排序等基础算法，是面试中的高频考点。

7. 实际工程应用

虽然题目简单，但其中包含的技术点在工程中广泛应用：

1. 日志去重：服务器日志分析时去除重复条目
2. 用户行为分析：统计独立访客(UV)
3. 数据清洗：处理脏数据中的重复项
4. 数据库优化：创建唯一索引避免重复数据

例如在统计网站UV时，可以使用类似的技术：

# 从日志中提取用户IP
ip_list = [log.ip for log in logs]
unique_ips = set(ip_list)
uv_count = len(unique_ips)

8. 面试实战建议

1. 白板编码练习：在纸上或白板上手写代码，锻炼表达能力
2. 复杂度分析：对每种解法都要能准确分析时间和空间复杂度
3. 测试用例设计：准备边界测试用例(空输入、极值、大量重复等)
4. 代码风格：注意变量命名、适当添加注释
5. 沟通技巧：边写边解释思路，展现思考过程

我在面试候选人时，发现很多人在简单题目上失分，不是因为不会做，而是忽略了边界条件或者无法清晰表达思路。建议平时练习时就要注意这些细节。