跳转至

3577. 统计计算机解锁顺序排列数

题目描述

给你一个长度为 n 的数组 complexity。

在房间里有 n 台 上锁的 计算机，这些计算机的编号为 0 到 n - 1，每台计算机都有一个 唯一 的密码。编号为 i 的计算机的密码复杂度为 complexity[i]。

编号为 0 的计算机密码已经 解锁 ，并作为根节点。其他所有计算机必须通过它或其他已经解锁的计算机来解锁，具体规则如下：

  • 可以使用编号为 j 的计算机的密码解锁编号为 i 的计算机，其中 j 是任何小于 i 的整数，且满足 complexity[j] < complexity[i]（即 j < i 并且 complexity[j] < complexity[i]）。
  • 要解锁编号为 i 的计算机，你需要事先解锁一个编号为 j 的计算机，满足 j < i 并且 complexity[j] < complexity[i]。

求共有多少种 [0, 1, 2, ..., (n - 1)] 的排列方式，能够表示从编号为 0 的计算机（唯一初始解锁的计算机）开始解锁所有计算机的有效顺序。

由于答案可能很大，返回结果需要对 109 + 7 取余数。

注意：编号为 0 的计算机的密码已解锁，而 不是 排列中第一个位置的计算机密码已解锁。

排列 是一个数组中所有元素的重新排列。

 

示例 1：

输入： complexity = [1,2,3]

输出： 2

解释：

有效的排列有：

  • [0, 1, 2]
    • 首先使用根密码解锁计算机 0。
    • 使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。
    • 使用计算机 1 的密码解锁计算机 2，因为 complexity[1] < complexity[2]。
  • [0, 2, 1]
    • 首先使用根密码解锁计算机 0。
    • 使用计算机 0 的密码解锁计算机 2，因为 complexity[0] < complexity[2]。
    • 使用计算机 0 的密码解锁计算机 1，因为 complexity[0] < complexity[1]。

示例 2：

输入： complexity = [3,3,3,4,4,4]

输出： 0

解释：

没有任何排列能够解锁所有计算机。

 

提示：

  • 2 <= complexity.length <= 105
  • 1 <= complexity[i] <= 109

解法

方法一：脑筋急转弯

由于编号为 \(0\) 的计算机密码已经被解锁，那么对于其他计算机 \(i\)，如果存在 \(\text{complexity}[i] \leq \text{complexity}[0]\)，则无法解锁计算机 \(i\)，因此返回 \(0\)。否则，排列可以是任意的，一共有 \((n - 1)!\) 种排列方式。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\text{complexity}\) 的长度。空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
8
9
class Solution:
    def countPermutations(self, complexity: List[int]) -> int:
        mod = 10**9 + 7
        ans = 1
        for i in range(1, len(complexity)):
            if complexity[i] <= complexity[0]:
                return 0
            ans = ans * i % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int countPermutations(int[] complexity) {
        final int mod = (int) 1e9 + 7;
        long ans = 1;
        for (int i = 1; i < complexity.length; ++i) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            ans = ans * i % mod;
        }
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        const int mod = 1e9 + 7;
        long long ans = 1;
        for (int i = 1; i < complexity.size(); ++i) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            ans = ans * i % mod;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func countPermutations(complexity []int) int {
    mod := int64(1e9 + 7)
    ans := int64(1)
    for i := 1; i < len(complexity); i++ {
        if complexity[i] <= complexity[0] {
            return 0
        }
        ans = ans * int64(i) % mod
    }
    return int(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function countPermutations(complexity: number[]): number {
    const mod = 1e9 + 7;
    let ans = 1;
    for (let i = 1; i < complexity.length; i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        ans = (ans * i) % mod;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn count_permutations(complexity: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let mut ans = 1i64;
        for i in 1..complexity.len() {
            if complexity[i] <= complexity[0] {
                return 0;
            }
            ans = ans * i as i64 % MOD;
        }
        ans as i32
    }
}

评论