997. 找到小镇的法官 (opens new window)

题目：

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。

如果小镇法官真的存在，那么：

1. 小镇法官不会信任任何人。
2. 每个人（除了小镇法官）都信任这位小镇法官。
3. 只有一个人同时满足属性 1 和属性 2 。

给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。

示例：

示例 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

提示：

• 1 <= n <= 1000
• 0 <= trust.length <= 104
• trust[i].length == 2
• trust 中的所有trust[i] = [ai, bi] 互不相同
• ai != bi
• 1 <= ai, bi <= n

解题：

方法一：计算各节点的入度和出度

本题需要用到有向图中节点的入度和出度的概念。在有向图中，一个节点的入度是指向该节点的边的数量；而一个节点的出度是从该节点出发的边的数量。

题干描述了一个有向图。每个人是图的节点，trust 的元素 trust[i] 是图的有向边，从 trust[i][0] 指向 trust[i][1]。我们可以遍历 trust，统计每个节点的入度和出度，存储在 inDegrees 和 outDegrees 中。

根据题意，在法官存在的情况下，法官不相信任何人，每个人（除了法官外）都信任法官，且只有一名法官。因此法官这个节点的入度是 n−1, 出度是 0。

我们可以遍历每个节点的入度和出度，如果找到一个符合条件的节点，由于题目保证只有一个法官，我们可以直接返回结果；如果不存在符合条件的点，则返回 −1。

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        // 定义入度和出度数组
        vector<int> inDegrees(n + 1);
        vector<int> outDegrees(n + 1);
        // 遍历trust数组，计算入度和出度
        for(auto& edge : trust) {
            int x = edge[0], y = edge[1];
            ++inDegrees[y];
            ++outDegrees[x];
        }
        // 遍历入度和出度数组，查找入度为n-1，出度为0的节点
        for(int i = 1; i <= n; ++i) {
            if(inDegrees[i] == n-1 && outDegrees[i] == 0) {
                return i;
            }
        }
        return -1;
    }
};

复杂度分析

• 时间复杂度：O(n+m)，其中 m 是 trust 的长度。首先需要遍历 trust 计算出 inDegrees 和 outDegrees，然后需要遍历 inDegrees 和 outDegrees 来确定法官。

• 空间复杂度：O(n)。记录各个节点的入度和出度需要 O(n) 的空间。

可调试的代码：

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        // 定义入度和出度数组
        vector<int> inDegrees(n + 1);
        vector<int> outDegrees(n + 1);
        // 遍历trust数组，计算入度和出度
        for(auto& edge : trust) {
            int x = edge[0], y = edge[1];
            ++inDegrees[y];
            ++outDegrees[x];
        }
        // 遍历入度和出度数组，查找入度为n-1，出度为0的节点
        for(int i = 1; i <= n; ++i) {
            if(inDegrees[i] == n-1 && outDegrees[i] == 0) {
                return i;
            }
        }
        return -1;
    }
};

int main() {
    Solution solution;
    // 小镇人数
    int n = 4;
    // 信任关系
    vector<vector<int>> trust = {{1, 3}, {1, 4}, {2, 3}, {2, 4}, {4, 3}};
    // 找到小镇法官
    int judge = solution.findJudge(n, trust);
    // 判断是否存在小镇法官
    if (judge != -1) {
        cout << "小镇法官的编号是: " << judge << endl;
    } else {
        cout << "没有找到小镇法官" << endl;
    }
    return 0;
}