leetcode
leetcode 901 ~ 950
找到小镇的法官

找到小镇的法官

难度:

标签:

题目描述

代码结果

运行时间: 51 ms, 内存: 19.3 MB


/* 思路:使用Java Stream流处理数据。我们将trust数组转换为两个映射表,然后检查每个人是否满足成为法官的条件。 */
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public int findJudge(int n, int[][] trust) {
    // 计算信任他人的次数
    Map<Integer, Long> trustCounts = Arrays.stream(trust)
        .map(t -> t[0])
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    
    // 计算被信任的次数
    Map<Integer, Long> trustedCounts = Arrays.stream(trust)
        .map(t -> t[1])
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    
    // 查找法官
    return IntStream.rangeClosed(1, n)
        .filter(i -> trustedCounts.getOrDefault(i, 0L) == n - 1 && trustCounts.getOrDefault(i, 0L) == 0)
        .findFirst()
        .orElse(-1);
}

解释

方法:

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

时间复杂度:

O(n*m)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在计算每个人的入度时,没有同时更新出度信息,而是在后面单独检查是否有出度?
在题解中,作者选择了在遍历入度数组后再单独检查是否有出度的方法,可能是为了简化第一次遍历的逻辑,使得代码更加易于理解和维护。这种方法首先通过一个遍历确定所有人的入度,然后再针对可能的候选人检查出度,从而确定是否为小镇法官。虽然这样做可能会略增加运行时间,但在代码的清晰性和结构上有优势。
🦆
在这个算法中,如果trust数组是空,但n大于1,这种情况下代码会如何处理?
如果trust数组为空且n大于1,意味着没有任何人信任其他人。在这种情况下,代码遍历trust时不会增加任何人的入度。然后在检查每个人的入度时,所有人的入度都为0,没有人达到n-1的入度,因此不满足成为法官的条件。所以,算法会返回-1,表示没有找到小镇法官。
🦆
算法中内部循环检查出度的效率是否可以优化,例如通过在遍历trust时直接记录每个人的出度?
是的,可以优化。在遍历trust数组的同时记录每个人的出度可以提高算法的效率。具体做法是,使用两个数组,一个记录入度,另一个记录出度。这样,在第一次遍历trust时就同时更新每个人的入度和出度。随后只需检查入度为n-1且出度为0的人,这样可以避免后续再进行一次可能的重复遍历,提高算法的整体效率。
🦆
对于输入n=1和trust为空的特殊情况,这种逻辑是否能正确返回法官的编号?
对于n=1且trust为空的情况,这意味着只有一个人且没有任何信任关系。根据法官的定义,法官是被所有其他人信任的唯一人选,同时不信任任何人。在这种情况下,这个唯一的人既没有信任别人也没有被别人信任,但理论上他/她符合法官的条件,因为不存在其他人。因此,算法应该返回这个唯一的人的编号,即1。如果算法没有特殊处理这种情况,可能会错误地返回-1。

相关问题

搜寻名人

搜寻名人