【Day 29 】2024-05-06 - 997. 找到小镇的法官

[azl397985856]

997. 找到小镇的法官

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/find-the-town-judge/

前置知识

• 图

  题目描述

  
  在一个小镇里，按从 1 到 n 为 n 个人进行编号。传言称，这些人中有一个是小镇上的秘密法官。

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

小镇的法官不相信任何人。 每个人（除了小镇法官外）都信任小镇的法官。 只有一个人同时满足条件 1 和条件 2 。

给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示编号为 a 的人信任编号为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的编号。否则，返回 -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

示例 4：

输入：n = 3, trust = [[1,2],[2,3]] 输出：-1

示例 5：

输入：n = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] 输出：3

 

提示：

1 <= n <= 1000 0 <= trust.length <= 104 trust[i].length == 2 trust[i] 互不相同 trust[i][0] != trust[i][1] 1 <= trust[i][0], trust[i][1] <= n

[zhiyuanpeng]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        d = collections.defaultdict(int)
        for k, v in trust:
            d[k] -= 1
            d[v] += 1
        for i in range(1, n+1):
            if d[i] == n-1:
                return i
        return -1

Time O(N) Space O(N)

[xil324]

class Solution(object): def findJudge(self, n, trust): """ :type n: int :type trust: List[List[int]] :rtype: int """ in_degree = [0] (n+1) out_degree = [0] (n+1) for item in trust: in_degree[item[1]] += 1 out_degree[item[0]] += 1 for i in range(1, n+1): if in_degree[i] == n - 1 and out_degree[i] ==0: return i return -1

[luzhaofeng]

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        lst1, lst2 = [], []
        for x, y in trust:
            lst1.append(x)
            lst2.append(y)
        l = list(set(range(1, n + 1)) - set(lst1))
        return l[0] if len(l) == 1 and lst2.count(l[0]) == n - 1 else -1

[Yukibei]

class Solution { public: int findJudge(int n, vector<vector>& trust) { vector inDegrees(n + 1); vector outDegrees(n + 1); for (auto& edge : trust) { int x = edge[0], y = edge[1]; ++inDegrees[y]; ++outDegrees[x]; } for (int i = 1; i <= n; ++i) { if (inDegrees[i] == n - 1 && outDegrees[i] == 0) { return i; } } return -1; } }; 复杂度分析 时间复杂度n+m 空间复杂度n

[maike-hps]

class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int: lst1, lst2 = [], [] for x, y in trust: lst1.append(x) lst2.append(y) l = list(set(range(1, n + 1)) - set(lst1)) return l[0] if len(l) == 1 and lst2.count(l[0]) == n - 1 else -1

[atom-set]

代码

var findJudge = function(n, trust) {
    const inDegrees = new Array(n + 1).fill(0);
    const outDegrees = new Array(n + 1).fill(0);
    for (const edge of trust) {
        const x = edge[0], y = edge[1];
        ++inDegrees[y];
        ++outDegrees[x];
    }
    for (let i = 1; i <= n; ++i) {
        if (inDegrees[i] === n - 1 && outDegrees[i] === 0) {
            return i;
        }
    }
    return -1;
};

复杂度分析

• 时间复杂度：O(n+m)
• 空间复杂度：O(n)

[Lizhao-Liu]

func findJudge(_ n: Int, _ trust: [[Int]]) -> Int {
    var trustTo = Array(repeating: 0, count: n + 1)
    var trusted = Array(repeating: 0, count: n + 1)

    for i in trust {
        trustTo[i[0]] += 1 // 统计每个人信任别人的次数
        trusted[i[1]] += 1 // 统计每个人被信任的次数
    }

    for i in 1...n {
        if trustTo[i] == 0 && trusted[i] == n - 1 {
            return i
        }
    }

    return -1
}

[Martina001]

class Solution { public int findJudge(int n, int[][] trust) { // 这题理解起来很简单，重点在于如何遍历一次就把信息存储下来 // 官方解答就比较直白，遍历一遍，把每个人的入度和出度都保存下来 再遍历这两个入/出度数组 找入度为n-1 出度为0的人即可 int inDegree[] = new int[n]; int outDegree[] = new int[n]; for(int i = 0; i < trust.length; i++) { int a = trust[i][0]; int b = trust[i][1]; inDegree[b-1]++; outDegree[a-1]++; } for(int i = 0; i < n; i++) { if(inDegree[i] == n-1 && outDegree[i] == 0){ return i+1; } } return -1; // return findJudge2(n, trust); }

/**
 * 写一下只用一个数组的实现
 * @param n
 * @param trust
 * @return
 */
public int findJudge2(int n, int[][] trust) {
    // 因为总共就n个人，所以直接用一个长度为n的数组就行
    int mixDegree[] = new int[n];
    for(int i = 0; i < trust.length; i++) {
        int a = trust[i][0];
        int b = trust[i][1];
        mixDegree[a-1]--;
        mixDegree[b-1]++;
    }
    for(int i = 0; i < n; i++) {
        // 全++ 无--  就是法官
        if(mixDegree[i] == n-1){
            return i+1;
        }
    }
    return -1;
}

}

[Hermione666]

class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int:

Create a list to track the trust score for each person

    trusted = [0] * n

    # Update trust scores based on the trust relationships
    for a, b in trust:
        trusted[a - 1] -= 1  # Person a trusts someone, decrement
        trusted[b - 1] += 1  # Person b is trusted by someone, increment

    # Identify the judge by checking if their trust score is n -1
    for i in range(n):
        if trusted[i] == n- 1:
            return i + 1  # Return the one-based index of the judge

    # If no judge is found, return -1
    return -1

[CathyShang]

图 统计入度；

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        if(trust.empty()&&n==1) return 1;
        unordered_map<int, int> cont;
        for(auto& relation : trust){
            cont[relation[0]] += -1; // 出
            cont[relation[1]] += 1;  // 入
        }
        int no_law = -1;
        for(auto& k:cont){
            if( k.second== n-1){
                no_law = k.first;
            }
        }
        return no_law;
    }
};

• Time O(N)
• Space O(N)