997.找到小鎮(zhèn)的法官

https://leetcode-cn.com/problems/find-the-town-judge/solution/997zhao-dao-xiao-zhen-de-fa-guan-ha-xi-b-x7eu/

難度：簡單

題目

在一個小鎮(zhèn)里，按從 1 到 n 為 n 個人進行編號。傳言稱，這些人中有一個是小鎮(zhèn)上的秘密法官。

如果小鎮(zhèn)的法官真的存在，那么：

1. 小鎮(zhèn)的法官不相信任何人。
2. 每個人（除了小鎮(zhèn)法官外）都信任小鎮(zhèn)的法官。
3. 只有一個人同時滿足條件 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。
通過這句話，我們可以得到結論：
假設村里有N個人，如果x為法官，則需要滿足：

1. 除X外的其他人都是村民，且其他人都信賴法官
2. 法官x不信賴任何人

知道這兩點，就足夠解題了。思路如下：

1. 首先我們維護一個包含 1 - N 的HashSet people，作為所有村民的集合
2. 然后維護一個HashMap judge 來作為可能是法官的人選，其中key為人員id，value為被信賴的人數(shù)
3. 遍歷trust
4. 如果trust[i][0] 在 people 中表示它是村民，因為他有信賴的人，刪除它
5. trust[i][1] 可能是法官，將其加入judge中，并將信賴人數(shù) += 1
6. 最終如果 people 長度不為1，表示有多個人未信任其他人，返回-1
7. 最終如果 people 長度1，則查看該人在 judge 中的信任度，是否為N - 1,即出他外的所有人都信任他
8. 如果7的結果為N - 1，表示他就是法官，返回people，否則返回 -1

投票解法
我們可以將這道題目理解為投票選舉的模式。
我們現(xiàn)在要選舉村民X，當法官，要求全村進行投票，X自己不能投票給任何人。
那么最終如果X能選舉上，表示他一共獲取了N - 1張票。
這樣的思維，我們維護一個全零數(shù)組li，然后遍歷trust變更index對應的村民value值。
待遍歷結束后，查看數(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

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown