题目重点：在保留首次出现顺序、O(1) 辅助空间约束下用读写指针和前缀线性查找。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版保留每个整数首次出现，输出顺序与首次出现顺序一致，直接原地缩短输入列表；允许 O(1) 个标量临时变量，不允许 HashSet 或辅助数组。
- 若面试官只要求返回有效前缀长度而不缩短原数组，可省略最后的尾部删除；手写快排会破坏原顺序，不能同时当成保序答案。
解题路线
- 维护 `numbers[:write]` 为已读元素的稳定去重结果。对每个 read 值，只在该前缀线性扫描是否存在；不存在才写到 `numbers[write]` 并递增 write。
- 归纳正确性：前缀初始为空；若值已出现，跳过保持每值第一次位置；若未出现，追加到前缀末尾保持相对顺序。读指针从不小于写指针，因此覆盖写不会丢未来未读元素。
- 扫描结束删去尾部，返回新长度。与哈希集法相比，严格保序加无额外结构时这种朴素解最坏 O(n²)；若可改输入顺序，可考虑原地排序后线性压缩，但已是不同契约。
- 9,841 个长度 ≤8、值域 {-1,0,1} 的数组用独立保序字典参考结果穷举对照。
手动走一遍
[3,1,3,2,1]：前缀依次 [3]、[3,1]，第二个 3 跳过，2 追加成 [3,1,2]，第二个 1 跳过。返回长度 3，输入原地成为 [3,1,2]。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def stable_dedup_in_place(numbers: list[int]) -> int:
"""Keep first occurrence order in numbers[:new_length]; use O(1) extra space."""
write = 0
for read in range(len(numbers)):
value = numbers[read]
duplicate = False
for previous in range(write):
if numbers[previous] == value:
duplicate = True
break
if not duplicate:
numbers[write] = value
write += 1
del numbers[write:]
return write
复杂度
最坏需比较 1+2+…+(n−1)=O(n²) 次，额外 O(1) 标量空间；Python 列表尾删除不需要另建输出列表。若允许 HashSet，可平均 O(n) 时间但需 O(u) 空间。
易错点与追问
容易失分的边界
- 把排序+相邻去重称为保留首次出现顺序。
- 用 HashSet 违反不使用额外数据结构的约束。
- 只给 O(n) 最优答案而不说明以空间换时间。
- 读写指针处理原地覆盖时未证明未读元素安全。
- 把面试官后续一句‘手写快排’误当成同一保序契约的一部分。
继续深挖
- 如果允许 O(n) 空间，如何做到平均 O(n) 时间？
- 如果允许改顺序且需 O(1) 空间，怎样利用堆排序与相邻压缩？
- 若数组已排序，如何 O(n) 时间 O(1) 空间去重？
- 若只返回前缀长度，如何避免物理删除尾部？
