C/C++哈希表优化LeetCode题解997找到小镇的法官

时间:2022-12-28 彤哥来刷题啦人气:0

方法一、哈希表

今天这道题比较简单，我们可以统计每个人信任别人的数量和被信任的数量，如果存在某个人信任别人的数量为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)。

运行结果如下：

方法二、优化

方法一中，我们使用了一个二维数组的第二维表示信任别人的数量和被别人信任的数量，其实，我们也可以使用一个一维数组来求解，减一表示信任别人的数量，加一表示被别人信任的数量，那么，只有法官才可能达到 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;
    }
}

时间复杂度：O(m)，m 为 trust 数组的长度。
空间复杂度：O(n)。

加载全部内容