LeetCode 634. 寻找数组的错位排列
目录
题目描述
题意分析
要什么：数组原本是
[1, 2, ..., n]，问有多少种重排方式，使得每一个位置上的数都和原来不同，答案对 $10^9 + 7$ 取模。
约束透露的信号：$n$ 可以到 $10^6$，而答案只是一个计数，说明不可能枚举排列，必须找出一个能在线性时间内递推的计数关系；同时「要求取模」几乎明示了答案是一个爆炸增长的组合数，中间乘法必须防溢出。
边界：$n = 1$ 时唯一的排列就是原样，没有任何合法方案，答案为 0；$n = 2$ 时只有交换这一种，答案为 1。这两个小规模值不是可有可无的特判，而是递推的起点。
解法：动态规划（递推公式）
核心思路
暴力做法是生成
1..n的全部排列再逐个检查每位是否错位，时间是 $O(n \cdot n!)$，$n$ 稍大就不可能跑完。
瓶颈在于我们其实并不需要方案本身，只需要方案的数量，而数量往往能靠「按第一个决策分类」递归地拆开。
关键观察是这样分类的：设f(n)表示1..n的错位排列数。考虑数字 1 最终落在哪个位置，它不能落在位置 1，所以有n - 1种选择，设它落在位置j。此时再看数字j的去向，恰好只有两种互不重叠的情形：
- 数字
j落在位置 1。于是 1 和j互换、彼此都已满足错位，剩下的n - 2个数字在各自的n - 2个位置上仍是一个规模为n - 2的同型子问题，方案数f(n - 2)。- 数字
j不落在位置 1。这时把「位置 1」临时看作「数字j的禁区」，那么剩下的n - 1个数字（含j）各自都有且只有一个禁止位置，结构与规模为n - 1的错位排列完全同构，方案数f(n - 1)。
两类相加再乘上j的n - 1种取法，得到状态定义与转移：f(i)= 长度为i的错位排列数，f(i) = (i - 1) * (f(i - 1) + f(i - 2))，初值f(1) = 0、f(2) = 1。
由于f(i)只依赖前两项，用两个滚动变量就够了，不必开长度为n的数组。
解题步骤
- 特判
n == 1返回 0、n == 2返回 1。为什么：递推从i = 3起才有意义，而f(1)、f(2)无法由公式导出（f(0)的组合意义要单独约定），直接给出更清晰也更安全。- 用两个
long变量d1 = f(1) = 0与d2 = f(2) = 1作为滚动窗口。为什么用 long：i - 1最大接近 $10^6$，而括号里的和已经被压在 $10^9$ 量级，两者相乘约 $10^{15}$，远超 32 位整数上限，用int会静默溢出成负数。- 从
i = 3循环到n，计算cur = (i - 1) * ((d2 + d1) % mod) % mod。为什么括号内要先取模：d1与d2各自小于 $10^9 + 7$，相加可能逼近 $2 \times 10^9$，先约掉一次模能把乘法的左因子压回 $10^9$ 以内，保证乘积安全落在 64 位范围。- 滚动更新
d1 = d2、d2 = cur。为什么顺序不能反：先写d2 = cur会让d1 = d2拿到已经被覆盖的新值，窗口错位一格，从第二轮起结果全错。- 返回
d2，即f(n)。为什么是d2不是d1：循环出口时d2始终代表刚算完的那一项，也就是f(n)；d1停在f(n - 1)。- 以
n = 4走一遍：初始d1 = f(1) = 0、d2 = f(2) = 1。i = 3时cur = 2 × (1 + 0) = 2，即f(3) = 2，对应[2,3,1]与[3,1,2]两种；滚动后d1 = 1、d2 = 2。i = 4时cur = 3 × (2 + 1) = 9，即f(4) = 9；滚动后d1 = 2、d2 = 9。循环结束返回 9。手工验证一下f(4) = 9的分类：数字 1 有 3 个位置可去，每种取法下「对换」贡献f(2) = 1种、「非对换」贡献f(3) = 2种，共3 × (1 + 2) = 9，与递推一致。
代码实现
// 核心实现：动态规划（递推公式），维护必要状态并避免重复处理。
class Solution {
public int findDerangement(int n) {
long mod = 1_000_000_007L;
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
long d1 = 0;
long d2 = 1;
for (int i = 3; i <= n; i++) {
long cur = (i - 1L) * ((d2 + d1) % mod) % mod;
d1 = d2;
d2 = cur;
}
return (int) d2;
}
}
// 核心实现：动态规划（递推公式），维护必要状态并避免重复处理。
func findDerangement(n int) int {
const mod int64 = 1_000_000_007
if n == 1 {
return 0
}
if n == 2 {
return 1
}
d1 := int64(0)
d2 := int64(1)
for i := 3; i <= n; i++ {
cur := int64(i-1) * ((d2 + d1) % mod) % mod
d1 = d2
d2 = cur
}
return int(d2)
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：从 3 到
n只循环一趟，每轮做常数次加法、乘法和取模，没有嵌套也没有递归重算。- 空间复杂度：$O(1)$。凭什么：全程只有
d1、d2、cur三个标量在滚动，转移只依赖前两项，因此不需要长度为n的 dp 数组。
关键点总结
- 计数类 DP 的通用套路是「对第一个自由决策做完备且互斥的分类」。本题分类的锚点不是位置 1 放谁，而是数字 1 去哪、以及被占位的那个数字是否回头对换，这种「两级分类」在错排、卡特兰数、装错信封问题里反复出现。
- 分类必须不重不漏：两个分支合起来覆盖数字
j的所有可能，且没有一种排列同时属于两类，这是加法原理成立的前提。面试里如果只能背出公式却讲不出这两类的划分依据，通常会被判定为没理解。- 只依赖前若干项的线性递推，一律可以从 $O(n)$ 空间降到 $O(1)$，代价是要格外小心滚动变量的更新顺序。
- 取模位置比取模本身更重要：模数放错地方虽然不报错，但会在大数据上悄悄给出错误答案。原则是「每次可能超范围的运算之后立刻取模，乘法之前先把因子压小」。
- 面试视角：被问到这题时，先说清
f(n) = (n-1)(f(n-1) + f(n-2))的组合意义，再补一句「也可以用容斥得到 $n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$，但涉及除法与逆元，递推更适合取模场景」，能直接体现深度。
易错点总结
- 错误写法：用
int存中间结果，写成int cur = (i - 1) * (d2 + d1) % mod；用例n = 100000→(i-1)与括号内的和相乘约 $10^{14}$，32 位整数溢出成负数，最终返回负值或随机数。- 错误写法：把取模放在乘法之外，写成
cur = ((i - 1) * (d2 + d1)) % mod且都是long；用例n = 1000000→(i-1)近 $10^6$、括号内近 $2 \times 10^9$，乘积约 $2 \times 10^{15}$ 尚未溢出 64 位，能侥幸通过，但只要把d1 + d2忘记先取模并连乘两轮就会越界，属于依赖运气的写法。- 错误写法：滚动变量更新顺序写反，先
d2 = cur再d1 = d2；用例n = 4→d1被赋成刚算出的 2 而不是 1，i = 4时算出3 × (2 + 2) = 12，正确答案是 9。- 错误写法：漏掉
n == 1的特判，直接让循环从 3 跑起并返回d2；用例n = 1→ 循环一次都不执行，返回初值d2 = 1，而正确答案是 0。- 错误写法：把初值设成
d1 = f(0) = 1、d2 = f(1) = 0却仍从i = 3起循环；用例n = 3→ 算出2 × (0 + 1) = 2看似巧合正确，但n = 4会用错位的窗口得到3 × (2 + 0) = 6，正确答案 9。窗口起点和循环起点必须成对匹配。- 错误写法：递推式记成
f(i) = (i - 1) * f(i - 1) + f(i - 2)（漏了括号）；用例n = 4→ 得到3 × 2 + 1 = 7，正确答案 9。- 错误写法：写成朴素递归
f(n) = (n-1) * (f(n-1) + f(n-2))不加记忆化；用例n = 40→ 调用次数呈斐波那契式指数增长直接超时；即便加了记忆化，n = 10^6的递归深度也会栈溢出。- 错误写法：返回时直接
return (int) d2但d2从未取模；用例n = 20→f(20)已是 18 位数，强转int截断成毫无意义的值。- 错误写法：用容斥公式
n! * Σ(-1)^k / k!并在取模下直接做除法；用例n = 10→ 模意义下/ k!不等于整数除法，必须换成乘以k!的模逆元，否则结果完全错误。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 同为二阶线性递推与滚动变量，但转移系数是常数而非随 i 变化 |
| 509. 斐波那契数 | 简单 | 递推形式最简，用来练矩阵快速幂把 $O(n)$ 压到 $O(\log n)$ |
| 96. 不同的二叉搜索树 | 中等 | 同样按「第一个决策」分类计数，但转移是卡特兰式的区间卷积求和 |