VMware Workstation Pro 16安装CentOS7与NAT配置
2026/10/1 9:43:17
LeetCode 634. 寻找数组的错位排列（Find the Derangement of An Array）
难度：中等
标签：数学、动态规划、组合数学
一、题目原文
给定一个整数n，原始数组是[1,2,3,…,n]。错位排列（derangement）是一种排列，要求：没有任何元素出现在它原来的位置上。
求该数组一共有多少种错位排列方案。
因为答案可能很大，请返回结果对109+710^9+7109+7取模。
示例
- 输入 n = 3，输出 = 2
原始数组 [1,2,3]
合法错位排列：[2,3,1]、[3,1,2]，一共2种 - 输入 n = 1，输出 = 0
数组 [1]，只能放在原位，没有错位方案 - 输入 n = 2，输出 = 1
原始 [1,2]，唯一错位：[2,1]
约束
1≤n≤1061 \le n \le 10^61≤n≤106
二、费曼学习法拆解思路（用大白话讲懂，像讲给小白）
费曼核心：不要直接甩公式，先举例子，分类讨论，再推递推式，再优化空间
1. 定义 D(n)
D(n)D(n)D(n)= n个数的错位排列总数。
基础边界（先看小例子找感觉）
- D(1) = 0：只有数字1，只能站原位，没法错位
- D(2) = 1：交换1、2，仅此1种
- D(3) = 2
- D(4) = 9
2. 推导递推公式（核心逻辑）
我们现在处理数字n，它不能放在第n个位置，所以它可以放在前面 n-1 任意一个位置（位置1，位置2 … 位置n-1），一共n-1种选择。
假设我们把数字n放到位置i。
现在分两种情况讨论数字i放哪里：
情况①：数字i放到位置n（n和i互相交换）
交换完，这两个数已经处理完毕。剩下还有 n-2 个数需要错位排列，方案数 = D(n-2)
情况②：数字i不能放到位置n
现在，数字i不能放位置n，其他数字也不能放自己原来位置。
等价：剩下 n-1 个数做错位排列，方案数 = D(n-1)
✅ 两种情况相加，并且前面有n-1种位置选择：
D(n)=(n−1)×[D(n−1)+D(n−2)]\boldsymbol{D(n) = (n-1) \times [D(n-1)+D(n-2)]}D(n)=(n−1)×[D(n−1)+D(n−2)]
取模：MOD=109+7MOD=10^9+7MOD=109+7
一句话记忆：第n个数字有n-1个坑可以放；放完之后要么两数互换剩D(n-2)，要么i被限制不能放n，变成D(n-1)。
3. 解法分类
- 递归（暴力，不可行）：会大量重复计算，n大直接栈溢出，时间爆炸
- DP数组：保存D(1),D(2)…D(n)，时间O(n)，空间O(n)
- 空间优化DP（推荐）：只保留前两项 D(n-1), D(n-2)，时间O(n)，空间O(1)，适配n到1e6上限
三、Python代码实现 + 逐行详细注释
解法1：空间优化DP（最优，O(n)时间，O(1)空间，推荐）
deffindDerangement(n:int)->int:# 定义取模常量，题目要求结果对10^9+7取模MOD=10**9+7# 边界条件ifn==1:# 只有1个元素，无法错位，直接返回0return0ifn==2:# [1,2]只能交换，1种方案return1# prev2 代表 D(n-2)，初始D(1)=0prev2=0# prev1 代表 D(n-1)，初始D(2)=1prev1=1# 从i=3一直循环计算到i=nforiinrange(3,n+1):# D(i) = (i-1) * (D(i-1)+D(i-2)) mod MODcurrent=((i-1)*(prev1+prev2))%MOD# 更新两个前置变量，准备下一轮循环# 原来的D(n-1)变成下一轮D(n-2)prev2=prev1# 当前计算得到D(i)，作为下一轮D(n-1)prev1=current# 循环结束，prev1就是D(n)returnprev1# 测试示例if__name__=="__main__":print(findDerangement(1))# 0print(findDerangement(2))# 1print(findDerangement(3))# 2print(findDerangement(4))# 9print(findDerangement(5))# 44解法2：DP数组版本（方便看完整序列，O(n)空间）
deffindDerangement_dp_array(n:int)->int:MOD=10**9+7ifn==1:return0# dp数组 dp[k] 代表k个数字的错位排列数量dp=[0]*(n+1)dp[1]=0# D(1)=0dp[2]=1# D(2)=1# 从3遍历到nforiinrange(3,n+1):dp[i]=((i-1)*(dp[i-1]+dp[i-2]))%MODreturndp[n]# 测试print(findDerangement_dp_array(4))# 9解法3：递归（仅教学，不适合大数据，会超时）
deffindDerangement_recursive(n:int)->int:MOD=10**9+7# 边界ifn==1:return0ifn==2:return1# 递推公式直接写递归return((n-1)*(findDerangement_recursive(n-1)+findDerangement_recursive(n-2)))%MOD# n超过20就明显变慢，n=1e6直接崩溃print(findDerangement_recursive(4))#9四、应用场景举例（错位排列真实使用场景）
场景1：密码/信封问题（经典错位排列原型）
有n封信，n个信封，每封信必须装错信封，求总共有多少种装法。
就是本题，D(n)就是全部装错的方案数。
场景2：抽奖，所有人不能抽到自己的礼物（交换礼物）
聚会n个人，每人准备一份礼物，随机抽签，任何人不能抽到自己准备的礼物，求总共有多少种抽法。
👉 直接调用findDerangement(n)。
场景3：测试用例生成、排列组合概率计算
求随机排列中，没有一个元素落在原位的概率：P=D(n)/n!P = D(n)/n!P=D(n)/n!
当n很大时，概率趋近1/e≈0.36791/e ≈ 0.36791/e≈0.3679（自然常数倒数，错位排列经典结论）。
比如n=100个人随机抽礼物，大约36.79%概率所有人都没有拿到自己的礼物。
场景4：哈希/置换密码、置换打乱算法
密码学里构造置换，要求置换中不存在不动点（没有元素映射到自身），需要统计这种置换总数，使用错位排列。
五、费曼复盘（检验你懂没懂，自问自答）
Q：D(n)公式怎么来的？
A：数字n有n-1个位置放，分两种情况：n和i互换，剩下n-2个；i不能放到n，剩下n-1个错位。相加 ×(n-1)。
Q：为什么要不断取模？
A：D(n)数值爆炸增长，n=1e6时数字极大，Python虽然支持大整数，但题目强制要求返回mod 1e9+7，中途取模防止数字过大拖慢运算。
Q：为什么递归不行？
A：递归重复计算D(n-1),D(n-2)，指数级时间；n稍微大一点栈溢出。迭代DP只向前保存两个变量，线性时间。
Q：n很大1e6，空间优化版本为什么能跑？
A：只存prev1、prev2两个变量，常数空间，循环1e6次Python可以快速跑完。