注：本文的代码实现使用的是 JS（JavaScript），为前端中想使用JS练习算法和数据结构的小伙伴提供解题思路。

描述

在一个小镇里，按从 1 到 n 为 n 个人进行编号。传言称，这些人中有一个是小镇上的秘密法官。如果小镇的法官真的存在，那么：

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

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

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

---

示例:

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

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

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

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

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

---

提示：

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

---

解题思路

直接法

按照体中所给的思路，

• 小镇的法官不相信任何人：说明trust[i]的第一个元素肯定不能是法官。
• 任何人(除了法官)都相信法官：说明trust[i]的第一个元素所构成的集合一定包括除了法官的所有人；且若法官存在，则一定在第二个元素所构成的集合中。

1. 因此，我们可以遍历trust数组，将普通人(除了法官的所有人)都添加到集合people中，把可能是法官的人添加到trusted集合中。

   	let people = new Set()
       let trusted = new Set()
       for(let i = 0, len = trust.length; i < len; i++){
           people.add(trust[i][0])
           trusted.add(trust[i][1])
       }
   

2. 然后我们需要找到people中没有的人alternative，因为他们很可能是法官

   	let alternative = []
       for(let i = 1; i <= n; i++)
           if(!people.has(i)) alternative.push(i)
   

3. alternative再和被信赖的人的集合trusted取交集，若交集只有一个元素，说明他基本上就是法官了；若不是一个元素，则一定没有法官

   	let rumors = alternative.filter(item => trusted.has(item))
       if(rumors.length !== 1) return -1
   

4. 最后检查是否所有人都信任法官，因为第一步中并不能保证所有人都信任法官

   let result = rumors[0]
       for(let i = 1; i <= n; i++){
           if(i !== result ) {
               if(!trust_str.has(i+''+result))
               return -1
           }
       }
   

   完整的代码如下：

   var findJudge = function(n, trust) {
   	// 如果就一个人且他谁也不相信，那他自己就是法官
       if(n === 1 && trust.length === 0) return 1
       let people = new Set()
       let trusted = new Set()
       // 为了最后一步判断是否每个人都相信法官用，所以把trust = [a,b]的形式转为字符串'ab'
       // 能够更好地判断 a 相信 b
       let trust_str = new Set()
       for(let i = 0, len = trust.length; i < len; i++){
           people.add(trust[i][0])
           trusted.add(trust[i][1])
           trust_str.add(trust[i].join(""))
       }
       let alternative = []
       for(let i = 1; i <= n; i++){
           if(!people.has(i)) alternative.push(i)
       }
       let rumors = alternative.filter(item => trusted.has(item))
       if(rumors.length !== 1) return -1
       let result = rumors[0]
       for(let i = 1; i <= n; i++){
           if(i !== result ) {
               if(!trust_str.has(i+''+result))
               return -1
           }
       }
       return result
   };
   

   这种方法纯粹就是根据脑子里的直观感受写出来的，因此算法很简单，按照逻辑写就可以了，期间的一些过程至于为什么，可能需要读者思考一下了。

图论法

我们可以将信任关系看成是一个图，a相信b，则可以认为有个a指向b的箭头。这样，如果有n个人，若b是法官，则有n-1个箭头指向b，且b不会指向任何人。也就是说，法官的入度为n-1出度为0。

使用对象存储入度与出度的方法如下：

var findJudge = function(n, trust) {
    if(n === 1 && trust.length === 0) return 1
    let in_obj = {}
    let out_obj = {}
    // 记录每个人的入度和出度
    for(let i = 0, len = trust.length; i< len; i++){
        if(out_obj.hasOwnProperty(trust[i][0])) out_obj[trust[i][0]] ++
        else out_obj[trust[i][0]] = 1
        if(in_obj.hasOwnProperty(trust[i][1])) in_obj[trust[i][1]] ++
        else in_obj[trust[i][1]] = 1
    }
    // 查找入度为 n-1 的人
    let in_set = new Set()
    for(const key in in_obj)
        if(in_obj[key] === n-1) in_set.add(key)
    // 在入度为 n-1 的人中，找出度为0的，也就是在 out_boj 中没出现过的
    for(const item of in_set)
        if(!(item in out_obj) return item
    // 没找到符合要求的
    return -1
};

使用数组存储入度与出度的方法如下：

var findJudge = function(n, trust) {
    let in_list = new Array(n+1).fill(0)
    let out_list = new Array(n+1).fill(0)
    for(const item of trust){
        in_list[item[1]] ++
        out_list[item[0]] ++
    }
    for(let i = 1; i <= n; i++)
        if(in_list[i] === n-1 && out_list[i] === 0)
            return i
    return -1
};