# 634. Find the Derangement of An Array

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.

There’s originally an array consisting of `n` integers from 1 to `n` in ascending order, you need to find the number of derangement it can generate.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

``````Input: 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
``````

Note:
`n` is in the range of [1, 106].

n = 1 时有 0 种错排

n = 2 时有 1 种错排 [2, 1]

n = 3 时有 2 种错排 [3, 1, 2], [2, 3, 1]

x x 4 x

x x 4 3

x x x

dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])

``````class Solution {
public:
int findDerangement(int n) {
if (n < 2) return 0;
vector<long long> dp(n + 1, 0);
dp[1] = 0; dp[2] = 1;
for (int i = 3; i <= n; ++i) {
dp[i] = (dp[i - 1] + dp[i - 2]) * (i - 1) % 1000000007;
}
return dp[n];
}
};
``````

``````class Solution {
public:
int findDerangement(int n) {
long long a = 0, b = 1, res = 1;
for (int i = 3; i <= n; ++i) {
res = (i - 1) * (a + b) % 1000000007;
a = b;
b = res;
}
return (n == 1) ? 0 : res;
}
};
``````

e[i] = -dp[i - 1] + (n - 1) * dp[i - 2] = -e[i - 1]

``````class Solution {
public:
int findDerangement(int n) {
long long res = 1;
for (int i = 1; i <= n; ++i) {
res = (i * res + (i % 2 == 0 ? 1 : -1)) % 1000000007;
}
return res;
}
};
``````

https://discuss.leetcode.com/topic/94429/o-n-short-java-code

https://discuss.leetcode.com/topic/94767/java-dp-solution-with-explanation

https://discuss.leetcode.com/topic/94421/java-solution-with-explanation-by-using-staggered-formula

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation