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

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

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

方法一、哈希表

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

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

請看代碼：

class Solution {
    public int findJudge(int n, int[][] trust) {
        // 不信任任何人的人 & 被所有人信任的人
        // 計算每個人信任的人的數(shù)量和被信任的數(shù)量
        // 前者等于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 數(shù)組的長度。
空間復雜度：O(n)。

運行結果如下：

方法二、優(yōu)化

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

請看代碼：

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
            // 且法官信任別人數(shù)量為 0
            // 所以，總的數(shù)量為 n-1
            if (arr[i] == n - 1) {
                return i;
            }
        }
                return -1;
    }
}