LeetCode 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,2,3,…,n]，如果该数组的一个排列中，每个数字都不在它原来的位置了，我们称这个排列是原数组的一个Derangement（错排）。问长度为n的数组，有多少个Derangement。 维基百科关于错排问题有比较详细的解释。 假设dp[n]表示长度为n的数组的错排个数，显然dp[0]=1,dp[1]=0,dp[2]=1。如果已经知道dp[0,…,n-1]，怎样求dp[n]。考虑第n个数，因为错排，它肯定不能放在第n位，假设n放在第k位，则有如下两种情况： 数字k放在了第n位，这时，相当于n和k交换了一下位置，还剩下n-2个数需要错排，所以+dp[n-2] 数字k不放在第n位，此时，可以理解为k原本的位置是n，也就是1不能放在第1位、2不能放在第2位、…、k不能放在第n位，也就相当于对n-1个数进行错排，所以+dp[n-1] 因为n可以放在1~n-1这n-1个位置，所以总的情况数等于dp[n]=(n-1)(dp[n-1]+dp[n-2])。 这就类似于求斐波那契数列的第n项了，维护前两个变量，不断滚动赋值就好了，时间复杂度O(n)，代码如下： [cpp] const int MOD = 1000000007; class Solution { public: int findDerangement(int n) { if (n == 0)return 1; if (n == 1)return 0; long long p = 0, pp = 1; for (int i = 2; i <= n; ++i) { long long cur = ((i – 1)*(p + pp)) % MOD; pp = p; p = cur; } return p; } }; [/cpp] 本代码提交AC，用时13MS。]]>