3577.统计计算机解锁顺序排列数：脑筋急转弯(组合数学)

【LetMeFly】3577.统计计算机解锁顺序排列数：脑筋急转弯(组合数学)

力扣题目链接：https://leetcode.cn/problems/count-the-number-of-computer-unlocking-permutations/

给你一个长度为 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到n-1的计算机，编号小且值小的可以解锁编号大且值大的，初始只有编号0（也就是给定序列中的第一个）是解锁状态，问解锁所有计算机有多少种解锁顺序（先解锁1号再解锁2号是一种，先解锁2号再解锁1号是另一种，至于它们是被谁解锁的不重要）。

转念一想发现，如果后面存在小于等于零号机的机器，则无论如何都不可能被解锁；反之若后面值都大于0号机，则后续任何一个机器想在任何次序(th)解锁都可以（都用0号去解锁就好了）。

具体方法

遍历一遍数组，如果有值小于等于数组中第一个元素，则返回0。

否则后面$len(complexity)-1$个机器的被解锁顺序可以按任意顺序排列，$(n-1)!$即为所求。

时空复杂度分析

  • 时间复杂度$O(n)$，其中$n=len(complexity)$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * @LastEditTime: 2025-12-10 22:56:22
 */
typedef long long ll;
const ll MOD = 1e9 + 7;
class Solution {
public:
    int countPermutations(vector<int>& complexity) {
        ll ans = 1;
        for (ll i = 1; i < complexity.size(); i++) {
            if (complexity[i] <= complexity[0]) {
                return 0;
            }
            ans = ans * i % MOD;
        }
        return static_cast<int>(ans);
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'''
LastEditTime: 2025-12-10 22:59:13
'''
from typing import List

class Solution:
    MOD = 1000000007

    def countPermutations(self, complexity: List[int]) -> int:
        ans = 1
        for i in range(1, len(complexity)):
            if complexity[i] <= complexity[0]:
                return 0
            ans = ans * i % self.MOD
        return ans

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * @LastEditTime: 2025-12-10 23:03:09
 */
class Solution {
    private long MOD = 1000000007;

    public int countPermutations(int[] complexity) {
        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;
    }
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * @LastEditTime: 2025-12-10 23:00:19
 */
package main

var MOD3577 int = 1000000007

func countPermutations(complexity []int) int {
    ans := 1
    for i := 1; i < len(complexity); i++ {
        if complexity[i] <= complexity[0] {
            return 0
        }
        ans = ans * i % MOD3577
    }
    return ans
}

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * @LastEditTime: 2025-12-10 23:06:41
 */
impl Solution {
    pub fn count_permutations(complexity: Vec<i32>) -> i32 {
        let mut ans: i64 = 1;
        let MOD: i64 = 1000000007;
        for i in 1..complexity.len() {
            if complexity[i] <= complexity[0] {
                return 0;
            }
            ans = ans * (i as i64) % MOD;
        }
        ans as i32
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

题解 > LeetCode
#题解 #中等 #数学 #数组 #LeetCode #组合数学 #脑筋急转弯
3577.统计计算机解锁顺序排列数：脑筋急转弯(组合数学)
https://blog.letmefly.xyz/2025/12/10/LeetCode 3577.统计计算机解锁顺序排列数/
作者
发布于
2025年12月10日
许可协议