跳转至

LeetCode: 634. 寻找数组的错位排列

1、题目描述

在组合数学中,如果一个排列中所有元素都不在原先的位置上,那么这个排列就被称为错位排列。

给定一个从 1n 升序排列的数组,你可以计算出总共有多少个不同的错位排列吗?

由于答案可能非常大,你只需要将答案对 10^9+7 取余输出即可。

样例 1:

输入: 3
输出: 2
解释: 原始的数组为 [1,2,3]。两个错位排列的数组为 [2,3,1] 和 [3,1,2]。

注释:

  • n 的范围是 [1, 10^6]

2、解题思路

  • 数学问题
f(n) = (n-1)*(f(n-1)+f(n-2))
class Solution:
    def findDerangement(self, n: int) -> int:
        mod_num = 1000000007
        if n == 1:
            return 0
        if n == 2:
            return 1

        pp, p = 0, 1

        for i in range(3, n + 1):
            pp, p = p , ((i - 1) * (pp + p)) % mod_num

        return p