搜寻名人
难度:
标签:
题目描述
代码结果
运行时间: 664 ms, 内存: 16.4 MB
/*
* 思路:
* 使用Java Stream简化对每个候选人的检查。
* 通过过滤和匹配来判断是否有满足名人条件的人。
*/
import java.util.stream.IntStream;
public class Solution {
public int findCelebrity(int n) {
return IntStream.range(0, n)
.filter(i -> IntStream.range(0, n).allMatch(j -> i == j || !knows(i, j) && knows(j, i)))
.findFirst()
.orElse(-1);
}
private boolean knows(int a, int b) {
// 这个方法由系统提供,模拟判断a是否认识b
return false; // 仅为示例,实际应根据系统实现
}
}
解释
方法:
这个题解使用了两次遍历来找到名人。第一次遍历从候选人0开始,将候选人与之后的每个人进行比较,如果候选人认识当前人,说明候选人不是名人,将当前人设为新的候选人。这样第一次遍历后,我们就能找出潜在的名人候选人。第二次遍历用来验证这个候选人是否真的是名人,即所有其他人都认识候选人,且候选人不认识任何其他人。同时使用了缓存来存储已经调用过的knows API结果,避免重复调用。
时间复杂度:
O(n)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在第一次遍历中,为什么遇到`candidate`认识`i`时,就立刻确定`candidate`不是名人,并将`i`设为新的候选人?是否有可能错过真正的名人?
▷🦆
第二次遍历中,`is_celebrity`函数调用`cache_knows`函数来验证候选人,如果`cache`中没有存储某次调用结果会怎样影响算法的性能和结果?
▷🦆
算法中提到使用缓存来存储`knows`API的结果以减少网络延迟,这种策略在哪些情况下最为有效?是否有可能因为缓存过多数据而影响性能?
▷相关问题
找到小镇的法官
小镇里有 n
个人,按从 1
到 n
的顺序编号。传言称,这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在,那么:
- 小镇法官不会信任任何人。
- 每个人(除了小镇法官)都信任这位小镇法官。
- 只有一个人同时满足属性 1 和属性 2 。
给你一个数组 trust
,其中 trust[i] = [ai, bi]
表示编号为 ai
的人信任编号为 bi
的人。
如果小镇法官存在并且可以确定他的身份,请返回该法官的编号;否则,返回 -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 <= 104
trust[i].length == 2
trust
中的所有trust[i] = [ai, bi]
互不相同ai != bi
1 <= ai, bi <= n