循环排序

01 / 共享的机制

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

01 / 一句话本质
当取值落在 [0, N] 或 [1, N] 时, 每个元素都知道自己的家在哪里 —— 扫一遍数组,只要 arr[i] 没在家, 就把它换回家。每次交换正好让一个元素就位,整轮 O(N)。
题目找出缺失的值输入[3, 0, 1, 4, 2]
arr
3
0
0
1
1
2
4
3
2
4
家位
0
1
2
3
4
数组长度 5,取值来自 0..5 且恰好缺一个。把每个值送回它的家位。
步
0 / 20
阶段
排序
缺失
·
0 / 20

02 / 模式骨架

# 把每个元素放到正确下标(范围 [0, n−1])i ← 0while i < n:home ← arr[i]if home < n and arr[home] ≠ home:swap arr[i], arr[home]else:i ← i + 1# 再扫一遍:arr[i] ≠ i 的位置就揭示了缺失的值

03 / 什么时候用这个模式

"数字范围 [0, N] / [1, N]"
最具辨识度的信号。取值范围与下标范围一致,每个值都有唯一合法的座位。下标和值说同一种语言。
"找缺失 / 重复 / 消失的数"
原地排好后,任何 arr[i] ≠ i 的位置要么对应一个缺失的数, 要么放着一个重复值 —— 最后一遍扫描就能读出答案。
"O(N) 时间、O(1) 额外空间"
这条约束排除了哈希集合和显式排序。循环排序只需一个交换计数器就能拿下两者。
"可修改的输入数组"
该模式会原地重排 arr。如果输入必须保留,要么先复制一份, 要么改用兄弟模式下标标记。

04 / 常见坑

i.
交换后立刻推进 i。
交换之后新的 arr[i] 也可能不在家 —— 推进前要再检查一次。 正确写法是 while (arr[i] 不在家) swap; else i++, 不能用普通的 for 循环。
ii.
混淆 [0, N] 与 [1, N] 的约定。
值范围是 [1, N] 时,v 的家是下标 v − 1; 值范围是 [0, N] 时,家就是下标 v。选定一种并保持一致 —— 这是本模式所有差一错误的根源。
iii.
重复值导致死循环。
如果两个相等的值都对应同一个家,反复交换会原地打转。 条件用 arr[i] != arr[home] 而不是 i != home —— 目标座位上已经坐着正确的人时,就别动它。

05 / 去 LeetCode 上练习

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

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

— / 什么时候用哪个

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