997.找到小鎮(zhèn)的法官
難度：簡單
題目
在一個小鎮(zhèn)里纱皆，按從 1 到 n 為 n 個人進行編號湾趾。傳言稱，這些人中有一個是小鎮(zhèn)上的秘密法官派草。
如果小鎮(zhèn)的法官真的存在搀缠，那么：
- 小鎮(zhèn)的法官不相信任何人。
- 每個人（除了小鎮(zhèn)法官外）都信任小鎮(zhèn)的法官近迁。
- 只有一個人同時滿足條件 1 和條件 2 艺普。
給定數(shù)組 trust，該數(shù)組由信任對 trust[i] = [a, b] 組成鉴竭，表示編號為 a 的人信任編號為 b 的人歧譬。
如果小鎮(zhèn)存在秘密法官并且可以確定他的身份，請返回該法官的編號搏存。否則瑰步，返回 -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缩焦。
通過這句話兵钮，我們可以得到結(jié)論：
假設村里有N個人，如果x為法官舌界，則需要滿足：
- 除X外的其他人都是村民，且其他人都信賴法官
- 法官x不信賴任何人
知道這兩點泰演，就足夠解題了呻拌。思路如下：
- 首先我們維護一個包含 1 - N 的HashSet people，作為所有村民的集合
- 然后維護一個HashMap judge 來作為可能是法官的人選睦焕，其中key為人員id藐握，value為被信賴的人數(shù)
- 遍歷trust
- 如果trust[i][0] 在 people 中表示它是村民，因為他有信賴的人垃喊，刪除它
- trust[i][1] 可能是法官猾普，將其加入judge中，并將信賴人數(shù) += 1
- 最終如果 people 長度不為1本谜，表示有多個人未信任其他人初家，返回-1
- 最終如果 people 長度1，則查看該人在 judge 中的信任度乌助，是否為N - 1,即出他外的所有人都信任他
- 如果7的結(jié)果為N - 1溜在，表示他就是法官，返回people他托，否則返回 -1
投票解法
我們可以將這道題目理解為投票選舉的模式掖肋。
我們現(xiàn)在要選舉村民X，當法官赏参，要求全村進行投票志笼，X自己不能投票給任何人。
那么最終如果X能選舉上把篓，表示他一共獲取了N - 1張票纫溃。
這樣的思維，我們維護一個全零數(shù)組li韧掩，然后遍歷trust變更index對應的村民value值皇耗。
待遍歷結(jié)束后，查看數(shù)組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;
}
}
歡迎關注我的公眾號: 清風Python郎楼，帶你每日學習Python算法刷題的同時，了解更多python小知識窒悔。
我的個人博客：https://qingfengpython.cn
