找到小镇的法官

难度: Easy

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

Submission

运行时间: 51 ms

内存: 19.3 MB

from typing import List

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        # 初始化入度数组，所有节点的入度初始为 0
        in_degree = [0] * (n + 1)
        
        # 遍历 trust 数组，统计每个节点的入度
        for a, b in trust:
            in_degree[b] += 1
        
        # 遍历入度数组，找到入度为 n-1 的节点，并检查是否有出度
        for i in range(1, n + 1):
            if in_degree[i] == n - 1:
                # 检查节点 i 是否有出度
                has_outdegree = False
                for a, b in trust:
                    if a == i:
                        has_outdegree = True
                        break
                if not has_outdegree:
                    return i  # 找到小镇法官
        
        return -1  # 没有找到小镇法官

Explain

此题解通过入度和出度的概念来确定小镇法官。每个人如果信任另一个人，被信任的人的入度增加，信任别人的人的出度也会存在。为了找到小镇法官，我们需要一个没有出度且入度为n-1的人。首先，将所有人的入度初始化为0，然后遍历信任列表增加相应的入度。之后，遍历所有人检查谁的入度为n-1同时没有出度，这个人即为小镇法官。如果没有这样的人，返回-1。

时间复杂度: O(n*m)

空间复杂度: O(n)

from typing import List

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        # 初始化入度数组，所有节点的入度初始为 0
        in_degree = [0] * (n + 1)
        
        # 遍历 trust 数组，统计每个节点的入度
        for a, b in trust:
            in_degree[b] += 1
        
        # 遍历入度数组，找到入度为 n-1 的节点，并检查是否有出度
        for i in range(1, n + 1):
            if in_degree[i] == n - 1:
                # 检查节点 i 是否有出度
                has_outdegree = False
                for a, b in trust:
                    if a == i:
                        has_outdegree = True
                        break
                if not has_outdegree:
                    return i  # 找到小镇法官
        
        return -1  # 没有找到小镇法官

Explore

在题解中，作者选择了在遍历入度数组后再单独检查是否有出度的方法，可能是为了简化第一次遍历的逻辑，使得代码更加易于理解和维护。这种方法首先通过一个遍历确定所有人的入度，然后再针对可能的候选人检查出度，从而确定是否为小镇法官。虽然这样做可能会略增加运行时间，但在代码的清晰性和结构上有优势。

如果trust数组为空且n大于1，意味着没有任何人信任其他人。在这种情况下，代码遍历trust时不会增加任何人的入度。然后在检查每个人的入度时，所有人的入度都为0，没有人达到n-1的入度，因此不满足成为法官的条件。所以，算法会返回-1，表示没有找到小镇法官。

是的，可以优化。在遍历trust数组的同时记录每个人的出度可以提高算法的效率。具体做法是，使用两个数组，一个记录入度，另一个记录出度。这样，在第一次遍历trust时就同时更新每个人的入度和出度。随后只需检查入度为n-1且出度为0的人，这样可以避免后续再进行一次可能的重复遍历，提高算法的整体效率。

对于n=1且trust为空的情况，这意味着只有一个人且没有任何信任关系。根据法官的定义，法官是被所有其他人信任的唯一人选，同时不信任任何人。在这种情况下，这个唯一的人既没有信任别人也没有被别人信任，但理论上他/她符合法官的条件，因为不存在其他人。因此，算法应该返回这个唯一的人的编号，即1。如果算法没有特殊处理这种情况，可能会错误地返回-1。