0997-找到小镇的法官

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

小镇里有 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。

代码

[sol1-Python3]
1
2
3
4
5
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        inDegrees = Counter(y for _, y in trust)
        outDegrees = Counter(x for x, _ in trust)
        return next((i for i in range(1, n + 1) if inDegrees[i] == n - 1 and outDegrees[i] == 0), -1)
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] inDegrees = new int[n + 1];
        int[] outDegrees = new int[n + 1];
        for (int[] 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;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int FindJudge(int n, int[][] trust) {
        int[] inDegrees = new int[n + 1];
        int[] outDegrees = new int[n + 1];
        foreach (int[] edge in 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;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> inDegrees(n + 1);
        vector<int> 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;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int findJudge(int n, int** trust, int trustSize, int* trustColSize){
    int* inDegrees = (int *)malloc(sizeof(int)*(n+1));
    int* outDegrees = (int *)malloc(sizeof(int)*(n+1));
    memset(inDegrees, 0, sizeof(int)*(n+1));
    memset(outDegrees, 0, sizeof(int)*(n+1));
    for (int i = 0; i < trustSize; ++i) {
        int x = trust[i][0], y = trust[i][1];
        ++inDegrees[y];
        ++outDegrees[x];
    }
    for (int i = 1; i <= n; ++i) {
        if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
            return i;
        }
    }
    return -1;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findJudge(n int, trust [][]int) int {
    inDegrees := make([]int, n+1)
    outDegrees := make([]int, n+1)
    for _, t := range trust {
        inDegrees[t[1]]++
        outDegrees[t[0]]++
    }
    for 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) 的空间。

 Comments
On this page
0997-找到小镇的法官