原文链接: https://leetcode-cn.com/problems/find-the-town-judge

英文原文

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

 

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Example 4:

Input: n = 3, trust = [[1,2],[2,3]]
Output: -1

Example 5:

Input: n = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

 

Constraints:

• 1 <= n <= 1000
• 0 <= trust.length <= 104
• trust[i].length == 2
• All the pairs of trust are unique.
• ai != bi
• 1 <= ai, bi <= n

中文题目

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

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

1. 小镇的法官不相信任何人。
2. 每个人（除了小镇法官外）都信任小镇的法官。
3. 只有一个人同时满足条件 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

通过代码

高赞题解

两个数组

思路

如果熟悉图的话，应该知道这是一道有向图问题。 并且法官👩‍⚖️ 实际上就是出度为0，入度为 N - 1的节点。

因此一个思路就是统计所有人的入度和出度信息，将满足出度为0，入度为 N - 1的节点输出。

这里用两个数组 in_degree 和 out_degree 分别记录入度和出度的信息，为了简单起见，我们初始化的数组长度为 N + 1，而不是 N。

具体算法如下：

• 遍历 trust，如果 trust[i] 为 [a, b] 说明 a 信任 b，那么更新 a 的出度 + 1，b 的入读 + 1。
• 遍历所有节点，将满足出度为0，入度为 N - 1的节点输出。

代码

class Solution:
     def findJudge(self, N, trust):
        in_degree = [0] * (N + 1)
        out_degree = [0] * (N + 1)
        for a, b in trust:
            in_degree[b] += 1
            out_degree[a] += 1
        for i in range(1, N + 1):
            if in_degree[i] == N - 1 and out_degree[i] == 0:
                return i
        return -1

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

一个数组

思路

上面的分析中指出了法官👩‍⚖️ 实际上就是出度为0，入度为 N - 1的节点。这固然没错，然而我们仍然可以换个角度来思考，法官👩‍⚖️ 同样是 入度 - 出度 == N - 1 的点，并且不是法官的人不可能是。

这样我们无需同时维护入度和出度的信息，转而维护入读和出度的差值即可。

代码

class Solution:
     def findJudge(self, N, trust):
        count = [0] * (N + 1)
        for i, j in trust:
            count[i] -= 1
            count[j] += 1
        for i in range(1, N + 1):
            if count[i] == N - 1:
                return i
        return -1

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

虽然时间复杂度没有变化，但是我们完成了常系数级别的优化，空间复杂度从 2 * N，下降到了 N。

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经30K star啦。

大家也可以关注我的公众号《力扣加加》获取更多更新鲜的LeetCode题解

统计信息

通过次数	提交次数	AC比率
39082	76580	51.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
搜寻名人	中等