997. 找到小镇的法官

997. 找到小镇的法官

力扣题目链接[1]

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

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

小镇法官不会信任任何人。每个人（除了小镇法官）都信任这位小镇法官。只有一个人同时满足属性 1 和属性 2 。给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

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

「示例 1：」

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

提示：

• 1 <= n <= 1000
• 0 <= trust.length <= 10^4
• trust[i].length == 2
• trust 中的所有trust[i] = [ai, bi] 互不相同
• ai != bi
• 1 <= ai, bi <= n

思路:

本题考查图的应用。按照题目描述，可以发现法官节点的特点是其余所有节点都指向它，而它不指向任何节点。

也就是说，法官的入度是n - 1 ，出度是0。

那么可以创建拥有N + 1个节点的图（数组），每个节点包含了出度和入度信息。至于为什么要多个节点，是因为题目是从1~n的顺序编号，多创建一个空节点，就不需要操心下标不对齐的问题了。

然后遍历二维数组，内层数组的第一项就是对应节点的出度，第二项就是对应节点的入度。

最后需要找出出度为0，入度为n - 1的节点，且要排除第一个节点，具体原因已经说明。最后返回该节点即可。

图

/**
 * @param {number} n
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(n, trust) {
    let graph = Array.from({ length: n + 1 }, () => ({ outDegree: 0, inDegree: 0 }));
    for (const [a, b] of trust) {
        graph[a].outDegree++;
        graph[b].inDegree++;
    }
    return graph.findIndex(({ outDegree, inDegree }, index) => {
        return index !== 0 && outDegree === 0 && inDegree === n - 1; 
    })
};

总结

本题涉及到图的相关概念。一般来说，图可分为有向图和无向图。有向图的所有边都有方向，即确定了顶点到顶点的一个指向；而无向图的所有边都是双向的，即无向边所连接的两个顶点可以互相到达。在一些问题中，可以把无向图当作所有边都是正向和负向的两条有向边组成。顶点的度是指和该顶点相连的边的条数。特别是对于有向图来说，顶点的出边条数称为该顶点的「出度」，顶点的入边条数称为该顶点的「入度」。而本题就是有向图，也引申出了出度和入度的概念。

这里使用数组来实现图这种数据结构，每一项都包含图中节点的入度信息和出度信息。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/problems/find-the-town-judge/