LeetCode Find the Derangement of An Array

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),代码如下:

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;
	}
};

本代码提交AC,用时13MS。

Leave a Reply

Your email address will not be published. Required fields are marked *