997. 找到小镇的法官
题目描述
小镇里有 n 个人，编号从 1 到 n。传闻其中有一人是法官。
法官需要同时满足两点：他不信任任何人；除他之外的每个人都信任他。满足这两点的人最多只有一个。
输入整数 n 和数组 trust，trust[i] = [ai, bi] 表示 ai 信任 bi。若法官存在且能确定是谁，返回他的编号；否则返回 -1。
示例 1
输入：n = 2, trust = [[1,2]] 输出：2
解释：1 信任 2，2 不信任任何人，所以 2 是法官。
示例 2
输入：n = 3, trust = [[1,3],[2,3]] 输出：3
解释：1 和 2 都信任 3，3 不信任别人。
示例 3
输入：n = 3, trust = [[1,3],[2,3],[3,1]] 输出：-1
解释：3 信任了 1，不符合法官条件，也没有其他人满足。
数据范围
1 <= n <= 10000 <= trust.length <= 10^4trust[i].length == 2trust中的数对两两不同。ai != bi1 <= ai, bi <= n
解题思路
把信任关系看作有向边 a → b。法官的入度必须是 n-1、出度必须是 0。只用一个数组 score：每条边让 a 的 score 减 1、让 b 的 score 加 1。score[i] = 入度 - 出度，它等于 n-1 当且仅当入度为 n-1 且出度为 0（入度最多 n-1）。最后找 score 等于 n-1 的人。
为什么正确
处理完前 k 条边后，score[i] 等于这 k 条边中 i 的入度减出度。
复杂度分析
时间 O(n + trust.length)，空间 O(n)。
易错点
只统计入度会出错：法官还必须不信任任何人。用入度减出度可以一次判断两条，因为只要出度至少为 1，score 就不可能达到 n-1。n=1 且没有信任关系时，唯一的人就是法官。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
score = [0] * (n + 1)
for a, b in trust:
score[a] -= 1
score[b] += 1
for i in range(1, n + 1):
if score[i] == n - 1:
return i
return -1class Solution {
public int findJudge(int n, int[][] trust) {
int[] score = new int[n + 1];
for (int[] t : trust) {
score[t[0]]--;
score[t[1]]++;
}
for (int i = 1; i <= n; i++) {
if (score[i] == n - 1) {
return i;
}
}
return -1;
}
}class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
vector<int> score(n + 1, 0);
for (auto& t : trust) {
score[t[0]]--;
score[t[1]]++;
}
for (int i = 1; i <= n; i++) {
if (score[i] == n - 1) {
return i;
}
}
return -1;
}
};func findJudge(n int, trust [][]int) int {
score := make([]int, n+1)
for _, t := range trust {
score[t[0]]--
score[t[1]]++
}
for i := 1; i <= n; i++ {
if score[i] == n-1 {
return i
}
}
return -1
}var findJudge = function(n, trust) {
const score = new Array(n + 1).fill(0);
for (const [a, b] of trust) {
score[a]--;
score[b]++;
}
for (let i = 1; i <= n; i++) {
if (score[i] === n - 1) {
return i;
}
}
return -1;
};function findJudge(n: number, trust: number[][]): number {
const score = new Array(n + 1).fill(0);
for (const [a, b] of trust) {
score[a]--;
score[b]++;
}
for (let i = 1; i <= n; i++) {
if (score[i] === n - 1) {
return i;
}
}
return -1;
}