2025-11-24：统计计算机解锁顺序排列数。用go语言，给定长度为 n 的数组 complexity，表示编号为 0 到 n

福大大架构师每日一题

发布于 2025-12-19 09:19:17

250

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2025-11-24：统计计算机解锁顺序排列数。用go语言，给定长度为 n 的数组 complexity，表示编号为 0 到 n-1 的 n 台计算机各自密码的复杂度（且复杂度两两不同）。

编号为 0 的计算机一开始已处于解锁状态，作为起点。

其余每台计算机 i 只能在此前已经解锁过某台编号为 j 的计算机的情况下被解开，且该 j 必须满足两点：j < i 且 complexity[j] < complexity[i]（索引和复杂度都比 i 小）。

现在要求统计有多少种由 0..n-1 全排列形成的顺序能对应一种合法的解锁过程（即在排列中，每出现的计算机 i 之前，必然已经出现过至少一个满足上述条件的 j）。

结果对 1000000007 取模返回。

注意：编号为 0 的计算机一开始就是解锁的，这并不等同于它在排列中必须位于首位。

2 <= complexity.length <= 100000。

1 <= complexity[i] <= 1000000000。

输入： 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]。

题目来自力扣3577。

过程步骤说明

1. 初始状态检查 计算机0是解锁过程的起点，一开始就处于解锁状态。在排列中，计算机0必须出现在第一个位置。这是因为任何其他计算机i（i > 0）被解锁时，都需要一个满足条件的j（j < i 且 complexity[j] < complexity[i]）已经出现在排列中。如果计算机0不是第一个出现，那么第一个出现的计算机i（i ≠ 0）之前不会有任何j出现（因为它是排列首元素），无法满足解锁条件，因此排列无效。所以，计算机0必须固定在第一位置。
2. 复杂度条件验证 对于每台计算机i（i从1到n-1），必须满足complexity[i] > complexity[0]。这是因为计算机0是唯一初始解锁的计算机，且其索引最小（j=0）。如果存在某个i使得complexity[i] ≤ complexity[0]，那么计算机0无法作为j满足complexity[j] < complexity[i]（因为复杂度相等或不满足小于关系）。同时，其他可能的j（索引小于i）也可能无法满足条件（因为解锁链依赖计算机0）。因此，一旦发现某个complexity[i] ≤ complexity[0]，直接返回0，表示没有有效排列。
- • 例如，在输入complexity = [1,2,3]中，所有i>0的复杂度（2和3）都大于complexity[0]=1，因此条件满足。
3. 计算有效排列数 如果所有i>0均满足complexity[i] > complexity[0]，则有效排列数就是其余n-1台计算机（索引1到n-1）的全排列数，即(n-1)!。原因如下：
- • 计算机0固定在第一位置。
- • 对于其他计算机，只要计算机0在排列首位，任意顺序排列均有效。因为对于任意i>0，计算机0（j=0）总是满足j < i且complexity[j] < complexity[i]，且计算机0已出现在i之前（因它位于首位）。因此，其他计算机的排列顺序没有额外约束。
- • 代码中通过循环从i=1到n-1，将结果ans依次乘以i（即计算1 × 2 × ... × (n-1)），并对10^9+7取模，得到(n-1)!。
4. 结果返回 最终返回计算得到的(n-1)!取模后的值。例如，对于complexity = [1,2,3]（n=3），(3-1)! = 2，输出为2，对应两个有效排列[0,1,2]和[0,2,1]。

时间复杂度和额外空间复杂度

• 总的时间复杂度：O(n) 算法需要遍历复杂度数组一次（从索引1到n-1），共n-1次循环。每次循环进行常数时间操作（比较和乘法取模），因此时间复杂度为线性O(n)。
• 总的额外空间复杂度：O(1) 除了输入的复杂度数组外，算法只使用了固定数量的变量（如ans、i和常量mod），不随输入规模n变化，因此额外空间复杂度为常数O(1)。

Go完整代码如下：

package main

import (
    "fmt"
)

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

func main() {
    complexity := []int{1, 2, 3}
    result := countPermutations(complexity)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def count_permutations(complexity):
    mod = 1_000_000_007
    ans = 1
    for i in range(1, len(complexity)):
        if complexity[i] <= complexity[0]:
            return0
        ans = (ans * i) % mod
    return ans

def main():
    complexity = [1, 2, 3]
    result = count_permutations(complexity)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>

using namespace std;

int countPermutations(vector<int>& complexity) {
    const int mod = 1'000'000'007;
    int ans = 1;
    for (int i = 1; i < complexity.size(); i++) {
        if (complexity[i] <= complexity[0]) {
            return 0;
        }
        ans = (1LL * ans * i) % mod;
    }
    return ans;
}

int main() {
    vector<int> complexity = {1, 2, 3};
    int result = countPermutations(complexity);
    cout << result << endl;
    return 0;
}