LeetCode 题解工作台
统计计算机解锁顺序排列数
给你一个长度为 n 的数组 complexity 。 在房间里有 n 台 上锁的 计算机，这些计算机的编号为 0 到 n - 1 ，每台计算机都有一个 唯一 的密码。编号为 i 的计算机的密码复杂度为 complexity[i] 。 编号为 0 的计算机密码已经 解锁 ，并作为根节点。其他所有计算机…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
由于编号为 的计算机密码已经被解锁，那么对于其他计算机 ，如果存在 $\text{complexity}[i] \leq \text{complexity}[0]$，则无法解锁计算机 ，因此返回 。否则，排列可以是任意的，一共有 $(n - 1)!$ 种排列方式。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个长度为 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 <= 1051 <= complexity[i] <= 109
解题思路
方法一：脑筋急转弯
由于编号为 的计算机密码已经被解锁，那么对于其他计算机 ，如果存在 ，则无法解锁计算机 ，因此返回 。否则，排列可以是任意的，一共有 种排列方式。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is dominated by sorting the array, giving O(n log n), and iterating to count unlock options adds O(n), resulting in overall O(n log n). Space complexity is O(1) additional or O(n) if storing sorted indices separately. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the root has the unique minimum complexity early.
- question_mark
Consider how duplicate complexities prevent unlocking sequences.
- question_mark
Expect the candidate to combine array traversal with combinatorial counting.
常见陷阱
外企场景- error
Not verifying that the first computer is the unique minimum complexity.
- error
Incorrectly counting unlock options for computers with equal complexity.
- error
Ignoring modulus arithmetic, leading to integer overflow on large arrays.
进阶变体
外企场景- arrow_right_alt
Allow unlocking only if complexity difference is at most k.
- arrow_right_alt
Count permutations where root is not fixed at index 0.
- arrow_right_alt
Consider circular unlocking order constraints instead of linear sequence.