Find the Derangement of An Array

发表于 | 分类于

Find the Derangement of An Array

题目描述：

给定一个数字n，表示用[1..n]组成排列组合。要求找到所有满足对应位置与其数不对应的情况。

例子：

具体描述见LeetCode634

解题思路：

主要的思路是动态规划，其中找到的规律是D[N] = (N - 1)*(D[N - 1] + D[N - 2]);我们可以理解为如下的解法：在对N个数进行排列时，第一个位置可以是N-1中选择，假设选择了X,而对应的X的位置上的位置可能是1，这种情况下一共有D[N - 2]可能；如果不是1的情况下则有D[N - 2]可能。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findDerangement(int n) {
        unsigned long long n1 = 0;
        unsigned long long n2 = 1;
        if (n == 1) return n1;
        if (n == 2) return n2;
        unsigned long long  res = 0;
        for (int i = 2; i < n; i++){
            res = (i)*(n1 + n2) % (1000000000 + 7);
            n1 = n2;
            n2 = res;
        }
        return res;       
    }
};