找到小镇的法官
难度:
标签:
题目描述
代码结果
运行时间: 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为空的特殊情况,这种逻辑是否能正确返回法官的编号?
▷