997. 找到小镇的法官 : 简单出度入度统计模拟题

题目描述

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

Tag : 「模拟」、「图论 出度入度」

在一个小镇里，按从 11 到 nn 为 nn 个人进行编号。传言称，这些人中有一个是小镇上的秘密法官。

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

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

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

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的编号。否则，返回 -1−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 <= 10001<=n<=1000
• 0 <= trust.length <= 10^40<=trust.length<=104
• trust[i].length == 2trust[i].length==2
• trust[i]trust[i] 互不相同
• trust[i][0] != trust[i][1]trust[i][0]!=trust[i][1]
• 1 <= trust[i][0], trust[i][1] <= n1<=trust[i][0],trust[i][1]<=n

模拟

今天起晚了 🤣

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

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

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

代码：

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;
    }
}
复制代码

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

最后

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

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

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

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