C/C++哈希表優(yōu)化LeetCode題解997找到小鎮(zhèn)的法官

更新時間：2022年12月28日 10:35:20 作者：彤哥來刷題啦

這篇文章主要為大家介紹了C/C++哈希表優(yōu)化題解997找到小鎮(zhèn)的法官示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

方法一、哈希表

今天這道題比較簡單，我們可以統(tǒng)計每個人信任別人的數量和被信任的數量，如果存在某個人信任別人的數量為0，且被信任的數量為 n-1，那么，這個人就是法官。

因為本題的數據范圍為 [1,1000]，數據范圍比較小，所以，直接使用數組作為哈希表來使用。

請看代碼：

class Solution {
    public int findJudge(int n, int[][] trust) {
        // 不信任任何人的人 & 被所有人信任的人
        // 計算每個人信任的人的數量和被信任的數量
        // 前者等于0，后者等于n-1
        int[][] arr = new int[n + 1][2];
        for (int[] t : trust) {
            // 0表示信任別人
            arr[t[0]][0]++;
            // 1表示被別人信任
            arr[t[1]][1]++;
        }
        
        for (int i = 1; i <= n; i++) {
            if (arr[i][0] == 0 && arr[i][1] == n - 1) {
                return i;
            }
        }
                return -1;
    }
}

時間復雜度：O(m)，m 為 trust 數組的長度。
空間復雜度：O(n)。

運行結果如下：

方法二、優(yōu)化

方法一中，我們使用了一個二維數組的第二維表示信任別人的數量和被別人信任的數量，其實，我們也可以使用一個一維數組來求解，減一表示信任別人的數量，加一表示被別人信任的數量，那么，只有法官才可能達到 n-1 的總數量。

請看代碼：

class Solution {
    public int findJudge(int n, int[][] trust) {
        // 不信任任何人的人 & 被所有人信任的人
        int[] arr = new int[n + 1];
        for (int[] t : trust) {
            // 減一表示信任別人
            arr[t[0]]--;
            // 加一表示被別人信任
            arr[t[1]]++;
        }
        
        for (int i = 1; i <= n; i++) {
            // 因為被別人信任不可能超過 n-1
            // 所以，只有法官能達到 n-1
            // 且法官信任別人數量為 0
            // 所以，總的數量為 n-1
            if (arr[i] == n - 1) {
                return i;
            }
        }
                return -1;
    }
}