题目重点：约 75 个乱序整数中稳定识别重复值，手写归并排序并说明零、空间和禁用库排序的边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版保留每个数第一次出现的值，把其后重复出现位置替为整数 0，然后对整个等长列表升序排序；原始 0 也是合法输入。
- 代码返回新列表、不修改输入；允许 O(n) 辅助空间，且禁止调用内置 sort 或手写 quicksort/bubblesort。若面试官要求原地或零放末尾，须调整输出规则。
解题路线
- 一遍维护 seen 集合：首见值原样放入结果，其后相同值写 0。原始 0 首次也是 0，之后重复 0 仍为 0，最终值列表无法区分两者，但排序目标仍确定。
- 手写 merge sort：递归二分，合并两个已排序子列；不会用题面提到的原生排序、quicksort 或 bubblesort。
- 如果额外空间被禁止，可考虑先原地排序后处理相邻重复，再重排零，但会改变‘保留第一次位置’这类潜在规则；需先问清楚。
- 训练实现对 97,656 个短数组用独立 O(n²) 首次出现判定加内置排序作为测试 oracle。
手动走一遍
[3,1,3,0,1] 首次 3/1/0 保留，第二个 3 与第二个 1 变 0，得到 [3,1,0,0,0]；升序结果 [0,0,0,1,3]。若题目希望所有原始零保留且新零有来源标签，单个整数 0 已不足以表达该信息。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def zero_duplicates_and_sort(values: list[int]) -> list[int]:
"""Keep first occurrence, replace later duplicates with zero, then sort."""
seen = set()
transformed = []
for value in values:
if value in seen:
transformed.append(0)
else:
seen.add(value)
transformed.append(value)
def merge_sort(items: list[int]) -> list[int]:
if len(items) <= 1:
return items[:]
middle = len(items) // 2
left = merge_sort(items[:middle])
right = merge_sort(items[middle:])
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
return merge_sort(transformed)
复杂度
判重平均 O(n) 时间、O(u) seen 空间；归并排序 O(n log n) 时间、O(n) 辅助空间，递归栈 O(log n)。输入约 75 只说明该样本规模，未给小值域，不能假设 counting sort 适用。
易错点与追问
容易失分的边界
- 把所有出现过重复的数连第一次也置零，和‘后续重复’契约不一致。
- 用系统 sort/内置 quicksort，违反公开限制。
- 不问原地和零输出位置，却把一种格式冒充原题唯一要求。
- 输入原本含 0 时把零视为占位符从判重集合排除。
- 声称 counting sort O(n) 却没有整数值域上界。
继续深挖
- 若要求原地 O(1) 额外空间，能否用堆排序并怎样标记重复？
- 如果只返回去重后的非零值加一个重复数量，如何减少空间？
- 若输入非常大而范围很小，计数排序何时合适？
- 如何保证原始 0 与重复替换出的 0 能被区分？
