How do I approach solving 'Find the Town Judge' efficiently?

Use array scanning to track trust relationships and a hash table for efficient lookups. Ensure no one trusts the judge and that the judge is trusted by all others.

What is the time complexity of the 'Find the Town Judge' problem?

The time complexity is O(n + m), where n is the number of people and m is the number of trust relationships.

How do I handle edge cases in this problem?

Ensure you account for scenarios where no trust relationships exist, or there is a cycle, and handle these cases by returning -1 when no judge is found.

What is the main pattern to solve 'Find the Town Judge'?

The solution uses a combination of array scanning to count trust relationships and hash table lookups to find the individual who is trusted by everyone but trusts no one.

Can 'Find the Town Judge' be solved with a graph approach?

Yes, the problem can also be seen as a graph problem where nodes represent people and edges represent trust. A valid judge corresponds to a node with no outgoing edges and in-degree of n-1.

#997

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找到小镇的法官

小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。如果小镇法官真的存在，那么：小镇法官不会信任任何人。每个人（除了小镇法官）都信任这位小镇法官。只有一个人同时满足属性 1 和属性 2 。给你一个数组 trust ，其中 trust[i] = [a i…

数组哈希表图

题目描述

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

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

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

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

如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -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⁴
trust[i].length == 2
trust 中的所有trust[i] = [a_i, b_i] 互不相同
a_i != b_i
1 <= a_i, b_i <= n

lightbulb

解题思路

方法一：计数

我们创建两个长度为 $n + 1$ 的数组 $cnt1$ 和 $cnt2$ ，分别表示每个人信任的人数和被信任的人数。

接下来，我们遍历数组 $trust$ ，对于每一项 $[a_i, b_i]$ ，我们将 $cnt1[a_i]$ 和 $cnt2[b_i]$ 分别加 $1$ 。

最后，我们在 $[1,..n]$ 范围内枚举每个人 $i$ ，如果 $cnt1[i] = 0$ 且 $cnt2[i] = n - 1$ ，则说明 $i$ 是小镇法官，返回 $i$ 即可。否则遍历结束后，返回 $-1$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $trust$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        cnt1 = [0] * (n + 1)
        cnt2 = [0] * (n + 1)
        for a, b in trust:
            cnt1[a] += 1
            cnt2[b] += 1
        for i in range(1, n + 1):
            if cnt1[i] == 0 and cnt2[i] == n - 1:
                return i
        return -1

speed

复杂度分析

指标	值
时间	complexity is O(n + m), where n is the number of people and m is the number of trust relationships. Space complexity is O(n) due to the hash table used for counting the trust relationships.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate may demonstrate understanding of array scanning combined with hash table usage.
question_mark
Pay attention to how efficiently the candidate handles edge cases like cyclic trust or no trust relationships.
question_mark
The problem is a good test of an interviewee's ability to optimize both time and space complexity.

warning

常见陷阱

外企场景

error
Ignoring edge cases such as no trust relationships or a cyclic trust relationship.
error
Failing to track both the number of people who trust an individual and the number of people an individual trusts.
error
Incorrectly assuming that multiple people can fulfill the judge criteria, missing the single judge requirement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem where some people can trust multiple individuals, but the judge still remains trusted by all.
arrow_right_alt
Solve the problem with a more constrained trust array, e.g., only half of the people trust others.
arrow_right_alt
Enhance the problem to consider negative trust, where someone can also actively distrust others.

help

常见问题

外企场景

继续练习

#928 尽量减少恶意软件的传播 II #924 尽量减少恶意软件的传播 #1311 获取你好友已观看的视频