[Leetcode][997. 找到小镇的法官] 图论,计算各节点的入度和出度

By Long Luo

Leetcode 997. 找到小镇的法官 题解。

方法一:图论

思路与算法:

  1. 如果存在法官,那么所有人都会信任法官,在结合条件11,可以得出信任法官的人数为n1n - 1
  2. 如果不存在法官,那么也可能存在某些人被所有人信任,这个人的信任人数也为n1n - 1,但是他也会信任别人
  3. 可以以此作为区分other和judge的条件,假设每个人都有信任值,那么定义一个数组长度为nn,用来存放nn个人的信任值:
  • 如果一个人信任了别人,那么这个人的信任值1-1
  • 如果一个人被别人信任,那么这个人的信任值+1+1

所以:

  1. 当一个人被所有人信任,并且他没有信任其它人时,这个人的信任值就是n1n - 1,那么此人就是法官;
  2. 当一个人被所有人信任,但是他也信任了其他人时,这个人的信任值<n1< n - 1
    其它情况下,每个人的信任值都会小于n1n - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findJudge(int N, int[][] trust) {
if (N <= 0) {
return -1;
} else if (N == 1) {
return 1;
}

// [0]: In [1]: Out
int[][] count = new int[N][2];
for (int[] item : trust) {
count[item[0] - 1][1]++;
count[item[1] - 1][0]++;
}

for (int i = 0; i < N; i++) {
if (count[i][0] == N - 1 && count[i][1] == 0) {
return i + 1;
}
}

return -1;
}

之后看来别人的题解才知道这道题其实考察的是图论的知识。

本题需要用到有向图中节点的入度和出度的概念。在有向图中,一个节点的入度是指向该节点的边的数量;而一个节点的出度是从该节点出发的边的数量。
题干描述了一个有向图。每个人是图的节点,trust\textit{trust}的元素trust[i]\textit{trust}[i]是图的有向边,从trust[i][0]\textit{trust}[i][0]指向trust[i][1]\textit{trust}[i][1]。我们可以遍历 trust\textit{trust},统计每个节点的入度和出度,存储在inDegrees\textit{inDegrees}outDegrees\textit{outDegrees}中。
根据题意,在法官存在的情况下,法官不相信任何人,每个人(除了法官外)都信任法官,且只有一名法官。因此法官这个节点的入度是n1n - 1, 出度是00
我们可以遍历每个节点的入度和出度,如果找到一个符合条件的节点,由于题目保证只有一个法官,我们可以直接返回结果;如果不存在符合条件的点,则返回1-1

复杂度分析

  • 时间复杂度:O(n+m)O(n+m),其中mmtrust\textit{trust}的长度。首先需要遍历trust\textit{trust}计算出inDegrees\textit{inDegrees}outDegrees\textit{outDegrees},然后需要遍历inDegrees\textit{inDegrees}outDegrees\textit{outDegrees}来确定法官。

  • 空间复杂度:O(n)O(n)。记录各个节点的入度和出度需要O(n)O(n)的空间。


All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗