循环排序

01 / 共享的机制

当取值落在已知范围 [0, N] 或 [1, N] 时,下标本身就是指针 —— 每个元素都自己知道该回到哪里。要么把它们逐个换回家完成排序,要么就地翻转符号来标记已见的下标, 就能在线性时间、常数额外空间里解决一整族「缺失 / 重复 / 消失」问题。

01 / 一句话本质
当取值落在 [1, N] 且只关心哪些下标出现过时, 数组本身就成了位集 —— 把 arr[|v|−1] 取负来标记 「下标 v−1 已见」。最后再扫一遍,仍为正的位置就是答案。
题目找出缺失的值输入[4, 3, 2, 7, 8, 2, 3, 1]
arr
4
0
3
1
2
2
7
3
8
4
2
5
3
6
1
7
1..n
1
2
3
4
5
6
7
8
长度 8 的数组,取值在 [1, 8]。下一步进入标记阶段:对每个值翻转其家位的符号。
步
0 / 26
阶段
标记
缺失
·
0 / 26

02 / 模式骨架

# 标记阶段 —— 把每个值对应的家位翻成负for i in 0..n−1:v ← abs(arr[i])if arr[v − 1] > 0:arr[v − 1] ← −arr[v − 1]# 读取阶段 —— 仍为正的位置揭示缺失的下标for i in 0..n−1:if arr[i] > 0: i + 1 从未出现

03 / 什么时候用这个模式

"取值为正,且不超过 n"
让符号翻转能安全承载一个额外比特位的前置条件。符号承担「已见」标志, 绝对值仍保留原数值。一个槽位,两条信息。
"缺失 / 重复 / 消失,O(1) 额外空间"
没有空间约束时哈希集合更简单。有这条约束,下标就成了唯一合法的存储 —— 符号翻转是最干净的用法。
"只关心出现与否,不要求物理就位"
不需要元素真的回到家,只需要恢复出哪些下标出现过。比完整的循环排序工作量更小。
"读取时记得取绝对值"
首次标记之后,数组里的值可能已是负数。计算家位时必须用绝对值:v = |arr[i]| —— 直接用原值会在第二次访问时算出错误的家位下标。

04 / 常见坑

i.
重复值导致二次取反。
如果 v 出现两次,直接取反会在第二次访问时把家位翻回正 —— 「已见」标记反而丢了。翻转前用 if arr[v−1] > 0 保护, 或在翻转前先读符号来探测重复。
ii.
读取时忘了 abs。
经过若干次标记后,arr[i] 自己可能已经是负的。计算家位下标时必须用 v = |arr[i]| —— 直接用原值要么会索引到负数区域崩溃, 要么悄悄改错另一个格子。
iii.
零和越界值。
这套技巧假设值在 [1, n] 之内。零没有可翻的符号,越界值的家也不存在 —— 要么预处理(例如把它们夹到 n + 1),否则标记阶段会悄悄污染数组。

05 / 去 LeetCode 上练习

四道题,按难度排序。这里有意不放解答。

01Find All Numbers Disappeared in an Array— LC 448简单→02Find All Duplicates in an Array— LC 442中等→03Find the Duplicate Number— LC 287中等→04First Missing Positive— LC 41困难→

— / 什么时候用哪个

经典循环排序
当输入可变且需要每个元素物理上回到它对应的下标位置时使用 —— 例如找出所有缺失或重复的值。
换回家 · LC 268 · LC 448
下标标记
当只关心每个下标是否出现过、想用一遍标记 + 一遍读取解决时使用 —— 把 arr[|x|−1] 取反来记录「已见」。
符号翻转 · LC 442 · LC 41