LC 997. 找到小镇的法官

题目描述

这是 LeetCode 上的 997. 找到小镇的法官 ，难度为 简单。

在一个小镇里，按从 1 到 n 为 n 个人进行编号。

传言称，这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在，那么：

• 小镇的法官不相信任何人。
• 每个人（除了小镇法官外）都信任小镇的法官。
• 只有一个人同时满足条件 1 和条件 24 。

给定数组 trust，该数组由信任对 $trust[i] = [a, b]$ 组成，表示编号为 a 的人信任编号为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的编号，否则，返回 -1。

示例 1：

输入：n = 2, trust = [[1,2]]

输出：2

示例 2：

输入：n = 3, trust = [[1,3],[2,3]]

输出：3

示例 3：

输入：n = 3, trust = [[1,3],[2,3],[3,1]]

输出：-1

示例 4：

输入：n = 3, trust = [[1,2],[2,3]]

输出：-1

示例 5：

输入：n = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]

输出：3

提示：

• $1 <= n <= 1000$
• $0 <= trust.length <= 10^4$
• $trust[i].length = 2$
• $trust[i]$ 互不相同
• $trust[i][0] != trust[i][1]$
• $1 <= trust[i][0], trust[i][1] <= n$

---

模拟

令 $m$ 为 trust 数组长度，对于每个 $trust[i] = (a, b)$ 而言，看作是从 $a$ 指向 $b$ 的有向边。

遍历 trust，统计每个节点的「入度」和「出度」：若存在 $a -> b$，则 $a$ 节点「出度」加一，$b$ 节点「入度」加一。

最后遍历所有点，若存在「入度」数量为 $n - 1$，且「出度」数量为 $0$ 的节点即是法官。

Java 代码：

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] in = new int[n + 1], out = new int[n + 1];
        for (int[] t : trust) {
            int a = t[0], b = t[1];
            in[b]++; out[a]++;
        }
        for (int i = 1; i <= n; i++) {
            if (in[i] == n - 1 && out[i] == 0) return i;
        }
        return -1;
    }
}

C++ 代码：

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> in(n + 1, 0), out(n + 1, 0);
        for (auto& t : trust) {
            int a = t[0], b = t[1];
            in[b]++; out[a]++;
        }
        for (int i = 1; i <= n; i++) {
            if (in[i] == n - 1 && out[i] == 0) return i;
        }
        return -1;
    }
};

Python 代码：

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        in_degree, out_degree = [0] * (n + 1), [0] * (n + 1)
        for a, b in trust:
            in_degree[b] += 1
            out_degree[a] += 1
        for i in range(1, n + 1):
            if in_degree[i] == n - 1 and out_degree[i] == 0:
                return i
        return -1

TypeScript 代码：

function findJudge(n: number, trust: number[][]): number {
    const inDegree = new Array(n + 1).fill(0), outDegree = new Array(n + 1).fill(0);
    for (const [a, b] of trust) {
        inDegree[b]++; outDegree[a]++;
    }
    for (let i = 1; i <= n; i++) {
        if (inDegree[i] === n - 1 && outDegree[i] === 0) return i;
    }
    return -1;
};

• 时间复杂度：$O(m + n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.997 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。