LeetCode 997. 找到小镇的法官

2025-05-16 HGNULB 约 11 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 997. 找到小镇的法官

题意分析

小镇里有 n 个人，编号 1 到 n。trust[i] = [a, b] 表示 a 信任 b。如果存在「法官」，他必须同时满足两个条件：他不信任任何人，并且其余 n - 1 个人都信任他。题目保证法官至多一位，返回他的编号，不存在则返回 -1。

要什么：一个编号。判定条件是两条硬性约束的合取，任何一条不满足就不是法官。

把它翻译成图：把每个人看成节点，[a, b] 看成一条从 a 指向 b 的有向边。那么「不信任任何人」就是出度为 0，「其余所有人都信任他」就是入度恰好为 $n-1$。于是问题变成：找一个出度为 0 且入度为 $n-1$ 的节点。这个建模一旦完成，题目就从文字游戏变成了度数统计。

更进一步的观察是本题的精髓：这两个条件可以被压缩成一个标量。定义每个人的分数为「入度减出度」，那么法官的分数是 $(n-1) - 0 = n - 1$。而任何非法官的人分数都严格小于 $n-1$——因为一个人的入度最多是 $n-1$（不能自己信任自己，题面保证 $a \ne b$），要想分数达到 $n-1$ 就必须入度取满 $n-1$ 且出度为 0，这恰好就是法官的定义。所以「分数等于 $n-1$」与「是法官」是充要的，用一个数组统计分数就够了，不必分别维护入度与出度两个数组。

约束透露的信号：$n$ 最多 1000，trust 的长度最多 $n(n-1)$ 约 $10^6$。规模不大，$O(n + m)$ 的线性扫描是显然的正解；反过来，trust 里保证不存在重复的信任对，这一点至关重要——如果允许重复，同一对关系被计两次会让分数虚高，「入度最多 $n-1$」的上界就不再成立，充要性论证随之崩塌。

边界：$n = 1$ 且 trust 为空时，唯一的居民自动满足「不信任任何人」且「其余 0 个人都信任他」，答案是 1；此时 $n - 1 = 0$，而他的分数恰好是 0，主逻辑自然命中，不需要特判。trust 可以为空数组。可能根本不存在法官，必须返回 -1。

解法：入度出度差值统计

核心思路

先看直译的做法：开两个数组 in 与 out 分别统计入度和出度，遍历 trust 时 out[a]++、in[b]++，最后找一个满足 in[i] == n - 1 && out[i] == 0 的 i。这个做法完全正确，时间空间都是最优量级，唯一的「问题」是它用了两个数组和两个判断条件。

能不能只用一个？关键在于论证「入度减出度」这个单一指标是否足以区分法官。

记第 i 个人的入度为 $d^-_i$、出度为 $d^+_i$，分数 $s_i = d^-_i - d^+_i$。由于题面保证 $a \ne b$ 且信任对不重复，任何人的入度上界是 $n - 1$（最多被其余每个人各信任一次），出度下界是 0。因此
\[s_i = d^-_i - d^+_i \le (n-1) - 0 = n - 1\]
等号成立当且仅当 $d^-_i = n-1$ 且 $d^+_i = 0$，这正是法官的两个条件。也就是说，$n-1$ 是分数的全局上界，而且只有法官能达到这个上界。于是两个条件被一个等式 score[i] == n - 1 完整刻画，一个数组、一个判断就够了。

顺着这条思路，具体实现变成一次差分式的累加：对每条边 [a, b]，执行 score[a]--（a 多信任了一个人，出度加一，分数减一）与 score[b]++（b 多被一个人信任，入度加一，分数加一）。整个 trust 扫完之后，score[i] 就等于第 i 个人的入度减出度。这里的不变量是：

在处理完 trust 的前 t 条关系后，score[i] 恰好等于「前 t 条关系中指向 i 的条数」减去「前 t 条关系中从 i 出发的条数」。

最后从 1 到 n 扫一遍，谁的分数等于 $n-1$ 就返回谁；一个都没有就返回 -1。由于上界论证保证了达到 $n-1$ 的人至多一位，找到即可立刻返回，不必担心有第二个候选。

数组开成 n + 1 长度而不是 n，是为了让下标与人的编号（1 到 n）直接对齐，省掉所有 -1 的换算——下标 0 空着不用，是一个用一格内存换零个下标错误的划算交易。

解题步骤

新建长度为 n + 1 的 score 数组。为什么多开一格：人的编号从 1 开始，让 score[i] 直接对应编号 i 可以彻底避免 score[a - 1] 这类换算，是下标错误的主要来源。数组默认全 0，恰好对应「还没统计任何关系时所有人的分数都是 0」。

遍历 trust，对每条 [a, b] 执行 score[a]-- 与 score[b]++。为什么减的是 a：a 信任别人，出度加一，按「入度减出度」的定义分数应当减一，这直接排除了任何有信任行为的人成为法官的可能。为什么加的是 b：b 被信任，入度加一。两个操作缺一不可——只加不减会让一个「既被所有人信任又信任别人」的人被误判为法官。

从 i = 1 遍历到 n，若 score[i] == n - 1 立刻返回 i。为什么用等于而不是大于等于：$n-1$ 已被证明是分数的上界，写成 >= 在正确输入下等价，但等号更准确地表达了「恰好取满」的语义。为什么可以立刻返回：达到上界的人至多一位，找到就是唯一解。

循环从 1 开始而不是 0：下标 0 不对应任何居民，它的分数恒为 0；当 $n = 1$ 时 $n - 1 = 0$，若从 0 开始扫会先命中下标 0 并返回 0，而正确答案是 1。这是本题最隐蔽的一位之差。

循环结束返回 -1。为什么不能返回 0：编号从 1 开始，0 不是合法编号，但用它表示「不存在」容易与真实答案混淆；题面指定的哨兵值是 -1。

以 具体用例 n = 3, trust = [[1,3],[2,3]] 走一遍，预期答案是 3。

初始化：score = [0, 0, 0, 0]（下标 0 到 3，下标 0 弃用）。

处理 [1,3]：1 信任 3。score[1]-- 得 -1；score[3]++ 得 1。数组变为 [0, -1, 0, 1]。
处理 [2,3]：2 信任 3。score[2]-- 得 -1；score[3]++ 得 2。数组变为 [0, -1, -1, 2]。

查找，目标分数是 $n - 1 = 2$：
i = 1：score[1] = -1，不等于 2。含义是 1 号信任了一个人却没被任何人信任，出度 1、入度 0，分数 $0 - 1 = -1$，与手工计算一致。
i = 2：score[2] = -1，同理不是。
i = 3：score[3] = 2，等于 $n - 1$，返回 3。核对：3 号被 1 和 2 信任（入度 2 = $n-1$），且从未信任任何人（出度 0），完全符合法官定义。

再走一个无解用例 n = 3, trust = [[1,3],[2,3],[3,1]]：
处理 [1,3] 后 score = [0,-1,0,1]；处理 [2,3] 后 score = [0,-1,-1,2]；处理 [3,1] 后 score[3]-- 得 1、score[1]++ 得 0，最终 score = [0,0,-1,1]。
查找目标 2：score[1] = 0、score[2] = -1、score[3] = 1，无一命中，返回 -1。正确——3 号虽然被所有人信任，但他自己也信任了 1 号，违反「不信任任何人」，那次 score[3]-- 精确地把他从候选中剔除了。这个例子最能说明「为什么必须同时做加和减」。

最后走一个边界用例 n = 1, trust = []：score = [0, 0]，目标分数 $n - 1 = 0$。循环从 i = 1 开始，score[1] = 0 命中，返回 1。正确——唯一的居民不信任任何人，且需要信任他的人有 0 个，条件平凡成立。注意若循环误从 i = 0 开始，会先命中弃用的下标 0 而返回 0。

代码实现

class Solution {
    // 对每条关系 a -> b，对 a 做 -1，对 b 做 +1，这样法官最终得分是 n - 1。
    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 {
    // 对每条关系 a -> b，对 a 做 -1，对 b 做 +1，这样法官最终得分是 n - 1。
    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
}

复杂度分析

时间复杂度：$O(n + m)$，其中 $m$ 是 trust 的长度。凭什么：第一趟遍历 trust 的每条关系各做两次自增自减，是 $O(m)$；第二趟遍历 n 个居民各做一次比较，是 $O(n)$。两趟都是线性且互不嵌套，没有任何重复扫描。相比「对每个人都遍历一遍 trust 验证两个条件」的 $O(nm)$ 做法，把乘法变成了加法。

空间复杂度：$O(n)$。凭什么：只额外开了一个长度 $n+1$ 的整型数组，与 trust 的规模无关——这正是「把关系压缩成度数统计」的收益，我们从不需要真的把图的邻接表建出来。若改用两个数组分别存入度与出度，空间常数会翻倍但量级不变。

关键点总结

先把文字描述翻译成图的语言。「不信任任何人」= 出度为 0，「所有人都信任他」= 入度为 $n-1$。这类社交关系题的第一步永远是把「谁对谁做了什么」映射成有向边，之后问题往往退化成度数或连通性的统计。

多个条件能否压缩成单一指标，取决于能否证明该指标的极值只由目标状态取到。这里的论证是：$s_i \le n-1$ 恒成立，且等号仅在「入度满、出度零」时成立。没有这个上界论证，用差值代替两个条件就是碰运气；面试时被追问「为什么一个数组就够」，要能立刻说出这段推导。

充要性依赖题面的隐含保证。「$a \ne b$」保证了不存在自环从而入度上界是 $n-1$，「信任对不重复」保证了同一条边不会被计两次。一旦放开其中任何一条，压缩成单指标的做法立刻失效，必须退回分别统计入度出度。读题时要专门确认这类保证。

用下标偏移换取零换算。编号从 1 开始就把数组开成 n + 1 长度、弃用下标 0，一格内存换掉所有 -1 的心智负担与出错可能，这是竞赛与工程中都值得固化的习惯。

哨兵返回值必须落在合法取值之外。编号范围是 1 到 n，所以「不存在」用 -1 表示；用 0 虽然当前也不冲突，但它是数组的合法下标，容易在后续维护中被误用。

面试视角：这题标为简单，但面试官问它通常不是为了看你会不会写循环，而是看两点：一是能否主动完成「社交关系 → 有向图度数」的建模，二是能否证明「分数等于 $n-1$」与「是法官」等价。建议的答法是先给出入度出度双数组的直白解，再说「注意到入度上界是 $n-1$，两个条件可以合并成一个差值」，最后补一句「这依赖题面保证没有自环且信任对不重复」。常见追问是「如果允许重复的信任对怎么办」——答「差值法失效，要么先对 trust 去重，要么退回分别统计并对入度做去重计数」。

易错点总结

错误写法：查找循环从 i = 0 开始 → 用例 n = 1, trust = []，目标分数是 0，弃用的下标 0 其分数恰好也是 0，会先命中并返回 0；正确答案是 1。编号从 1 开始，下标 0 必须跳过。

错误写法：只写 score[t[1]]++ 而漏掉 score[t[0]]-- → 用例 n = 3, trust = [[1,3],[2,3],[3,1]]，3 号的分数被算成 2 而命中，返回 3；但 3 号信任了 1 号，不满足「不信任任何人」，正确答案是 -1。减法这一步正是排除有出度者的唯一手段。

错误写法：判定写成 score[i] == n → 用例 n = 3, trust = [[1,3],[2,3]]，法官的分数是 2 而非 3，无一命中返回 -1；正确答案是 3。信任他的人是其余 $n-1$ 个，法官不会信任自己。

错误写法：数组开成 new int[n] 并用 score[t[0]] 直接索引 → 用例 n = 2, trust = [[1,2]]，编号 2 对应下标 2 而数组长度只有 2，直接数组越界异常。编号从 1 开始时数组必须开 n + 1 长。

错误写法：判定写成 score[i] >= n - 1 → 在题面保证下与 == 等价，但一旦输入含重复信任对（例如 trust = [[1,2],[1,2]]，n = 2），2 号分数被算成 2 超过了 $n-1 = 1$，>= 会把他误判为法官。用 == 表达「恰好取满上界」的语义更严格。

错误写法：找到候选后不返回而继续扫描，最后返回最后一个候选 → 逻辑上因为候选至多一位而不会出错，但一旦输入不满足保证就会返回错误的那个；且白白多扫了剩余部分。上界论证已保证唯一，找到即返回。

错误写法：为每个人单独遍历一遍 trust 来验证两个条件 → 用例 $n = 1000$、trust 长度 $10^6$ 时是 $10^9$ 次比较，直接超时。度数统计的价值就在于把 $O(nm)$ 变成 $O(n + m)$。

错误写法：用 HashMap<Integer, Integer> 代替数组存分数，并在查找时遍历 map 的键 → 用例 n = 1, trust = []，map 是空的，遍历不到任何键，返回 -1；正确答案是 1。从未出现在 trust 里的人分数为 0，但 map 中没有对应条目，必须遍历 1 到 n 而不是遍历 map。

错误写法：把 trust[i] 理解成「b 信任 a」而写成 score[t[0]]++、score[t[1]]-- → 用例 n = 3, trust = [[1,3],[2,3]]，3 号分数被算成 -2、1 号和 2 号各为 1，无一等于 2，返回 -1；正确答案是 3。方向必须与题面定义一致。

错误写法：无解时返回 0 → 用例 n = 3, trust = [[1,3],[2,3],[3,1]]，返回 0 会被误读成编号为 0 的人是法官；题面规定不存在时返回 -1。

相似题目

题目	难度	考察点
277. 搜寻名人	中等	同样的度数定义，但关系只能通过 API 逐次询问，需先用一趟扫描淘汰出唯一候选
1615. 最大网络秩	中等	也靠度数统计，但要枚举点对并扣掉两点之间被重复计算的那条边
207. 课程表	中等	入度用于拓扑排序的队列驱动，考的是环检测而非单点的度数极值
210. 课程表 II	中等	在拓扑排序基础上要输出完整的合法顺序，入度归零的时机决定了入队顺序
1466. 重新规划路线	中等	需要同时保留原始方向与反向边，从 0 出发遍历时按方向决定是否计数
684. 冗余连接	中等	关注的是无向图中成环的那条边，靠并查集判定两端是否已连通