难度: Medium
Submission
运行时间: 150 ms
内存: 15.9 MB
class Solution:
def findDerangement(self, n: int) -> int:
MOD = 10 ** 9 + 7
if n == 0 or n == 1:
return 0
if n == 2:
return 1
f1 = 1
f2 = 0
for i in range(3, n + 1):
f1, f2 = (i - 1) * (f1 + f2) % MOD, f1
return f1
Explain
这个题解使用动态规划的思想来解决错位排列问题。我们用 f[i] 表示长度为 i 的数组的错位排列数目，那么可以得到递推式：f[i] = (i-1) * (f[i-1] + f[i-2])。这是因为我们可以考虑数字 i 放在哪里：如果把 i 放在某个位置，其余 i-1 个数有 f[i-1] 种错位排列方式；如果不把 i 放在任何位置，那么就相当于求 i-1 个数的错位排列数，即 f[i-2]。为了避免重复计算和节省空间，我们可以只用两个变量 f1 和 f2 来分别表示 f[i-1] 和 f[i-2]，并在每次循环中更新它们的值。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findDerangement(self, n: int) -> int:
MOD = 10 ** 9 + 7
if n == 0 or n == 1:
return 0
if n == 2:
return 1
f1 = 1 # f[i-1]
f2 = 0 # f[i-2]
for i in range(3, n + 1):
# 根据递推式 f[i] = (i-1) * (f[i-1] + f[i-2]) 更新 f1 和 f2
f1, f2 = (i - 1) * (f1 + f2) % MOD, f1
return f1
Explore
这个递推式基于错位排列的定义和组合思考。错位排列意味着数组中没有一个元素出现在其原始位置上。考虑将元素`i`放入数组的错位排列中：1) 如果我们把元素`i`置于除了最后一个位置外的任何一个位置（共有`i-1`个选择），那么剩下的`i-1`个元素中的每一个也不能出现在它的原始位置上，即`f[i-1]`；2) 我们也可以考虑将元素`i`放在最后一个位置，这时我们需要将前`i-1`个元素进行错位排列，即`f[i-2]`。因此，`f[i]`的值由这两部分组成，`(i-1)`代表元素`i`可以选择的位置数量（除去它自己的原始位置），`f[i-1] + f[i-2]`代表在这些位置选择后，其他元素的错位排列数量。
基础情况是理解错位排列的起点。对于`f[0]`，考虑一个空数组，没有元素进行错位排列，因此结果为0。对于`f[1]`，只有一个元素的数组不能满足错位排列的条件，因为唯一的元素只能放在它的原始位置，故也是0。而对于`f[2]`，包含两个元素的数组，唯一的错位排列是将这两个元素互换位置，因此错位排列数为1。这些基础情况为递推式提供了初始值，使得我们可以计算更大的`n`值。
模`10**9 + 7`的选择是基于几个方面的考虑。首先，这是一个大质数，可以有效避免在计算过程中的冲突和整数溢出问题。其次，由于这个数接近于`10^9`，它在计算机中可以高效地处理，同时保持良好的性能特性。最后，`10**9 + 7`是在编程竞赛和算法实现中常用的模数，因此在算法设计中使用该模数有助于保持一致性和标准化。