By Long Luo

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

方法一：图论

思路与算法：

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

• 如果一个人信任了别人，那么这个人的信任值\(-1\)
• 如果一个人被别人信任，那么这个人的信任值\(+1\)

所以：

1. 当一个人被所有人信任，并且他没有信任其它人时，这个人的信任值就是\(n - 1\)，那么此人就是法官；
2. 当一个人被所有人信任，但是他也信任了其他人时，这个人的信任值\(< n - 1\)。 其它情况下，每个人的信任值都会小于\(n - 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;
}

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

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

复杂度分析

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

• 空间复杂度：\(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. 😉😃💗