思路
我们可以将其抽象为图结构,如下所示。顶点 3 表示法官,其余为百姓。信任关系用边表示,比如边 1 → 3 1 \rightarrow 3 1→3 表示 1 信任 3。
顶点 1245 之间可能也存在边,我们先不用管。
此处补充一下出度入度的概念:
- 出度:从某点出发的边数
- 入度:指向某点的边数
根据题意,如果小镇法官存在,那么:
- 小镇法官不会信任任何人。
- 每个人(除了小镇法官)都信任这位小镇法官。
- 只有一个人同时满足属性 1 和属性 2。
记 n n n 为点数。所以在图结构中,如果存在小镇法官,只有他对应的顶点满足:
- 出度为 0 0 0
- 入度为 n − 1 n - 1 n−1
综上,我们遍历边集,对每条边的起点和终点统计出度入度就可以了。
代码
C++
class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
// 多存储一个顶点 0,方便处理。
vector<int> outDegrees(n + 1); // 出度
vector<int> inDegrees(n + 1); // 入度
for (auto& edge : trust) {
int from = edge[0], to = edge[1]; // 起点和终点
outDegrees[from]++; // 起点出度 + 1
inDegrees[to]++; // 终点入度 + 1
}
// 忽略顶点 0,寻找出度为 0,入度为 n-1 的顶点。
for (int i = 1; i <= n; ++i) {
if (outDegrees[i] == 0 && inDegrees[i] == n - 1){
return i;
}
}
return -1;
}
};
C
int findJudge(int n, int** trust, int trustSize, int* trustColSize){
// 多存储一个顶点 0,方便处理。
int* outDegrees = (int *)malloc(sizeof(int)*(n+1)); // 出度
int* inDegrees = (int *)malloc(sizeof(int)*(n+1)); // 入度
memset(inDegrees, 0, sizeof(int)*(n+1));
memset(outDegrees, 0, sizeof(int)*(n+1));
for (int i = 0; i < trustSize; ++i) {
int from = trust[i][0], to = trust[i][1]; // 起点和终点
outDegrees[from]++; // 起点出度 + 1
inDegrees[to]++; // 终点入度 + 1
}
// 忽略顶点 0,寻找出度为 0,入度为 n-1 的顶点。
for (int i = 1; i <= n; ++i) {
if (outDegrees[i] == 0 && inDegrees[i] == n - 1) {
return i;
}
}
return -1;
}
Python3
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
# 多存储一个顶点 0,方便处理。
out_degrees = [0] * (n + 1) # 出度
in_degrees = [0] * (n + 1) # 入度
for start, end in trust: # 遍历每条边的起点和终点
out_degrees[start] += 1 # 起点出度 + 1
in_degrees[end] += 1 # 终点入度 + 1
# 忽略顶点 0,寻找出度为 0,入度为 n-1 的顶点。
for i in range(1, n + 1):
if out_degrees[i] == 0 and in_degrees[i] == n - 1:
return i
return -1
Python3 +语法糖
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
outDegrees = Counter(start for start, _ in trust)
inDegrees = Counter(end for _, end in trust)
return next((i for i in range(1, n + 1) if outDegrees[i] == 0 and inDegrees[i] == n - 1), -1)
Java
class Solution {
public int findJudge(int n, int[][] trust) {
// 多存储一个顶点 0,方便处理。
int[] outDegrees = new int[n + 1]; // 出度
int[] inDegrees = new int[n + 1]; // 入度
for (int[] edge : trust) {
int from = edge[0]; // 起点
int to = edge[1]; // 终点
outDegrees[from]++; // 起点出度 + 1
inDegrees[to]++; // 终点入度 + 1
}
// 忽略顶点 0,寻找出度为 0,入度为 n-1 的顶点。
for (int i = 1; i <= n; i++) {
if (outDegrees[i] == 0 && inDegrees[i] == n - 1) {
return i;
}
}
return -1;
}
}
Kotlin
class Solution {
fun findJudge(n: Int, trust: Array<IntArray>): Int {
// 多存储一个顶点 0,方便处理。
val outDegrees = IntArray(n+1) // 出度
val inDegrees = IntArray(n+1) // 入度
for((from, to) in trust){ // 遍历每条边的起点和终点
outDegrees[from]++ // 起点出度 + 1
inDegrees[to]++ // 终点入度 + 1
}
// 忽略顶点 0,寻找出度为 0,入度为 n-1 的顶点。
return (1..n).firstOrNull{
outDegrees[it] == 0 && inDegrees[it] == n-1
}
?: -1
}
}
复杂度
读者不熟悉 Θ \Theta Θ 视为 O O O 即可。
记 n n n 为点数, m m m 为边数
时间复杂度: Θ ( n + m ) \Theta(n + m) Θ(n+m)。此处不能化简,因为小镇法官可能不存在,我们不能确定 m m m 与 n n n 的大小关系。
空间复杂度: Θ ( n ) \Theta(n) Θ(n)
推广
借助理论知识能较方便地处理很多模型,这和数学中的函数很像,也是理论科学的魅力所在。也希望读者能重视基础知识,不用急于做题。很多题目中所要求解的就是学术中的术语,比如“岛屿数量”这道经典题目求的就是连通分量数目。
以下均为个人所著,兼顾了面试、本科、硕士阶段,包含清晰的 PPT 动画展示以及配套的练习题。读者也在陆续写其他算法教程。