Easy

题目描述

在一个小镇里，有 n 个人，标号从 1 到 n。有传言说这些人中有一个是小镇的法官。

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

  1. 小镇法官不相信任何人。
  2. 除了小镇法官外，所有人都信任小镇法官。
  3. 有且仅有一个人同时满足条件 1 和条件 2。

给定一个数组 trust，其中 trust[i] = [ai, bi] 表示标号为 ai 的人信任标号为 bi 的人。如果 trust 数组中不存在信任关系，那么这种信任关系就不存在。

如果小镇法官存在并且可以确定身份，请返回小镇法官的标号。否则，返回 -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 <= 10^4
  • trust[i].length == 2
  • 所有的信任关系都是唯一的
  • ai != bi
  • 1 <= ai, bi <= n

解题思路

这是一个图论问题，可以将信任关系看作有向图中的边。法官的特点是：入度为 n-1（所有其他人都信任他），出度为 0（他不信任任何人）。

解法一：度数统计法（推荐） 我们可以用一个数组记录每个人的"信任度"，定义为：被信任的次数 - 信任他人的次数。对于法官来说，这个值应该是 n-1（被所有其他人信任，自己不信任任何人）。

具体步骤：

  1. 初始化一个数组 degree，记录每个人的信任度
  2. 遍历 trust 数组，对于每个信任关系 [a, b]：
    • degree[a] -= 1（a 信任了别人）
    • degree[b] += 1（b 被别人信任）
  3. 找到 degree 值为 n-1 的人，即为法官

解法二：入度出度分别统计 分别统计每个人的入度和出度，然后找到入度为 n-1 且出度为 0 的人。

第一种解法更简洁，时间复杂度相同，是推荐解法。

代码实现

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> degree(n + 1, 0);
        
        for (auto& t : trust) {
            degree[t[0]]--; // 信任他人，度数减1
            degree[t[1]]++; // 被信任，度数加1
        }
        
        for (int i = 1; i <= n; i++) {
            if (degree[i] == n - 1) {
                return i;
            }
        }
        
        return -1;
    }
};

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        degree = [0] * (n + 1)
        
        for a, b in trust:
            degree[a] -= 1  # 信任他人，度数减1
            degree[b] += 1  # 被信任，度数加1
        
        for i in range(1, n + 1):
            if degree[i] == n - 1:
                return i
        
        return -1

public class Solution {
    public int FindJudge(int n, int[][] trust) {
        int[] degree = new int[n + 1];
        
        foreach (int[] t in trust) {
            degree[t[0]]--; // 信任他人，度数减1
            degree[t[1]]++; // 被信任，度数加1
        }
        
        for (int i = 1; i <= n; i++) {
            if (degree[i] == n - 1) {
                return i;
            }
        }
        
        return -1;
    }
}

var findJudge = function(n, trust) {
    const degree = new Array(n + 1).fill(0);
    
    for (const [a, b] of trust) {
        degree[a]--; // 信任他人，度数减1
        degree[b]++; // 被信任，度数加1
    }
    
    for (let i = 1; i <= n; i++) {
        if (degree[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(E + N)E 为 trust 数组长度，N 为人数。需要遍历所有信任关系和所有人
空间复杂度O(N)需要额外数组存储每个人的信任度

相关题目