解法
思路和算法
使用已解锁的计算机密码将未解锁的计算机解锁的条件是：已解锁的计算机的编号和密码复杂度分别小于未解锁的计算机的编号和密码复杂度。由于初始时只有编号为 $0$ 的计算机密码已解锁，编号 $0$ 是最小编号，因此对于其他任意编号 $i$，是否可以使用编号为 $0$ 的计算机密码解锁编号为 $i$ 的计算机的情况如下。
如果存在 $1 \le i < n$ 的整数 $i$ 满足 $\textit{complexity}[i] \le \textit{complexity}[0]$，则对于任意可以被编号为 $0$ 的计算机密码解锁的计算机的编号 $j$，必有 $\textit{complexity}[j] > \textit{complexity}[0]$，因此 $\textit{complexity}[j] > \textit{complexity}[i]$，即编号为 $j$ 的计算机密码不能解锁编号为 $i$ 的计算机。因此，编号为 $i$ 的计算机无法被解锁，此时无法解锁所有计算机。
如果 $1 \le i < n$ 的所有整数 $i$ 都满足 $\textit{complexity}[i] > \textit{complexity}[0]$，则所有计算机都能被编号为 $0$ 的计算机密码解锁。由于初始时编号为 $0$ 的计算机密码已解锁，因此其余 $n - 1$ 台计算机可以按任意顺序解锁，排列数是 $(n - 1)!$。
代码
###Java
class Solution {
static final int MODULO = 1000000007;
public int countPermutations(int[] complexity) {
long permutations = 1;
int n = complexity.length;
for (int i = 1; i < n; i++) {
if (complexity[i] <= complexity[0]) {
return 0;
}
permutations = permutations * i % MODULO;
}
return (int) permutations;
}
}
###C#
public class Solution {
const int MODULO = 1000000007;
public int CountPermutations(int[] complexity) {
long permutations = 1;
int n = complexity.Length;
for (int i = 1; i < n; i++) {
if (complexity[i] <= complexity[0]) {
return 0;
}
permutations = permutations * i % MODULO;
}
return (int) permutations;
}
}
###C++
const int MODULO = 1000000007;
class Solution {
public:
int countPermutations(vector<int>& complexity) {
long long permutations = 1;
int n = complexity.size();
for (int i = 1; i < n; i++) {
if (complexity[i] <= complexity[0]) {
return 0;
}
permutations = permutations * i % MODULO;
}
return permutations;
}
};
###Python
MODULO = 1000000007
class Solution:
def countPermutations(self, complexity: List[int]) -> int:
permutations = 1
n = len(complexity)
for i in range(1, n):
if complexity[i] <= complexity[0]:
return 0
permutations = permutations * i % MODULO
return permutations
###C
const int MODULO = 1000000007;
int countPermutations(int* complexity, int complexitySize) {
long long permutations = 1;
for (int i = 1; i < complexitySize; i++) {
if (complexity[i] <= complexity[0]) {
return 0;
}
permutations = permutations * i % MODULO;
}
return permutations;
}
###Go
const MODULO = 1000000007
func countPermutations(complexity []int) int {
permutations := 1
n := len(complexity)
for i := 1; i < n; i++ {
if complexity[i] <= complexity[0] {
return 0
}
permutations = permutations * i % MODULO
}
return permutations
}
###JavaScript
const MODULO = 1000000007;
var countPermutations = function(complexity) {
let permutations = 1;
let n = complexity.length;
for (let i = 1; i < n; i++) {
if (complexity[i] <= complexity[0]) {
return 0;
}
permutations = permutations * i % MODULO;
}
return permutations;
};
###TypeScript
const MODULO = 1000000007;
function countPermutations(complexity: number[]): number {
let permutations = 1;
let n = complexity.length;
for (let i = 1; i < n; i++) {
if (complexity[i] <= complexity[0]) {
return 0;
}
permutations = permutations * i % MODULO;
}
return permutations;
};
复杂度分析
登录
