LeetCode 997. 找到小镇的法官
题目描述
题意分析
法官必须同时满足两个条件：自己不信任任何人，其他
n-1人全部信任自己。返回法官编号，不存在则返回-1。把“
a信任b”看作有向边a → b，两个条件分别对应出度为 0、入度为n-1。题目保证没有自我信任，且同一信任关系不会重复出现。
解法：入度出度差值统计
核心思路
[!blue]
用一个数组同时表达两个条件：
score[i] = 入度 - 出度。遇到一条a信任b的关系，就给a减一分，给b加一分。为什么只检查
score[i] == n-1就够了？没有重复关系和自环，保证一个人的入度最多为n-1；出度又不可能小于 0。因此差值达到上限n-1，只能是入度恰好为n-1且出度恰好为 0，正好同时满足法官的两个条件。反过来，真正的法官也一定得到这个分数。统计完所有关系后，从编号 1 到
n找这个分数即可。不可能出现两个满足条件的人：如果二者都是法官，其中一人既必须信任另一人，又必须不信任任何人，产生矛盾。当
n = 1且没有信任关系时，唯一居民的分数为 0，恰好等于n-1，可以直接被同一套判断选出，无需特殊分支。
解题步骤
- 建立长度为
n+1的零初始化数组，直接用居民编号作为下标。- 遍历每条
[a, b]，执行score[a]--和score[b]++。- 全部关系统计完成后，扫描编号
1...n。- 若某人的分数等于
n-1，返回该编号；全部扫描后仍未找到则返回-1。
代码实现
class 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;
}
}
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
}
复杂度分析
设信任关系数量为
m。
- 时间复杂度：$O(n+m)$，遍历全部关系，再扫描全部居民；数组初始化也为 $O(n)$。
- 空间复杂度：$O(n)$，只需一份分数数组。
关键点总结
[!green]
- 分数等于入度减出度，达到上限时必然同时满足满入度和零出度。
- 这一等价关系依赖题目保证：关系不重复，且不存在自我信任。
- 居民编号从 1 开始，只有处理完全部关系后才能确定最终分数。
易错点总结
[!yellow]
- 只统计被信任次数：无法排除也信任别人的候选人。
- 关系方向写反：信任别人应减分，被别人信任才加分。
- 统计过程中分数达到目标就返回：后面的关系可能让这个人产生出度，最终分数会下降。
- 从编号 0 开始找：0 不是居民编号，尤其在
n = 1时可能误返回它。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 277. 搜寻名人 | 中等 | 法官与名人都要求所有人指向它且它不指向别人，本题信任边直接给出，原题通过接口查询关系。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！