997.找到小镇的法官
难度：简单
题目
在一个小镇里，按从 1 到 n 为 n 个人进行编号。传言称，这些人中有一个是小镇上的秘密法官。
如果小镇的法官真的存在，那么：
- 小镇的法官不相信任何人。
- 每个人（除了小镇法官外）都信任小镇的法官。
- 只有一个人同时满足条件 1 和条件 2 。
给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示编号为 a 的人信任编号为 b 的人。
如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的编号。否则，返回 -1。
提示：
- 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
示例
示例 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 和条件 2。
通过这句话，我们可以得到结论：
假设村里有N个人，如果x为法官，则需要满足：
- 除X外的其他人都是村民，且其他人都信赖法官
- 法官x不信赖任何人
知道这两点，就足够解题了。思路如下：
- 首先我们维护一个包含 1 - N 的HashSet people，作为所有村民的集合
- 然后维护一个HashMap judge 来作为可能是法官的人选，其中key为人员id，value为被信赖的人数
- 遍历trust
- 如果trust[i][0] 在 people 中表示它是村民，因为他有信赖的人，删除它
- trust[i][1] 可能是法官，将其加入judge中，并将信赖人数 += 1
- 最终如果 people 长度不为1，表示有多个人未信任其他人，返回-1
- 最终如果 people 长度1，则查看该人在 judge 中的信任度，是否为N - 1,即出他外的所有人都信任他
- 如果7的结果为N - 1，表示他就是法官，返回people，否则返回 -1
投票解法
我们可以将这道题目理解为投票选举的模式。
我们现在要选举村民X，当法官，要求全村进行投票，X自己不能投票给任何人。
那么最终如果X能选举上，表示他一共获取了N - 1张票。
这样的思维，我们维护一个全零数组li，然后遍历trust变更index对应的村民value值。
待遍历结束后，查看数组li中是否有value值为N - 1的人即可。
模拟解法
Python:
class Solution: def findJudge(self, n, trust): people, judge = set(range(1, n + 1)), defaultdict(int) for p, j in trust: if p in people: people.remove(p) judge[j] += 1 if len(people) != 1: return -1 person = people.pop() return -1 if judge.get(person, 0) != n - 1 else person
Java:
class Solution { public int findJudge(int n, int[][] trust) { HashSet<Integer> people = new HashSet<>(); HashMap<Integer, Integer> judge = new HashMap<>(); for (int i = 1; i < n + 1; i++) { people.add(i); } for (int[] condition : trust) { int p = condition[0]; int j = condition[1]; people.remove(p); judge.put(j, judge.getOrDefault(j, 0) + 1); } if (people.size() != 1) { return -1; } int person = people.iterator().next(); return judge.getOrDefault(person, 0) == n - 1 ? person : -1; } }
投票解法
Python:
class Solution: def findJudge(self, n, trust): li = [0] * (n + 1) for i, j in trust: li[i] -= 1 li[j] += 1 for i in range(1, n + 1): if li[i] == n - 1: return i return -1
Java:
class Solution { public int findJudge(int n, int[][] trust) { int[] li = new int[n + 1]; for (int[] condition : trust) { li[condition[0]]--; li[condition[1]]++; } for (int i = 1; i < n + 1; i++) { if (li[i] == n - 1) { return i; } } return -1; } }
