找出知晓秘密的所有专家
难度:
标签:
题目描述
代码结果
运行时间: 229 ms, 内存: 63.6 MB
/*
* Problem: Given n experts, an array of meetings with [xi, yi, timei], and a firstPerson,
* find all experts who will know the secret after all meetings are done.
*
* Approach:
* 1. Use a set to keep track of experts who know the secret.
* 2. Use streams to sort meetings by time and process them.
* 3. Initialize the set with expert 0 and firstPerson knowing the secret at time 0.
* 4. For each meeting, if either participant knows the secret, add both to the set.
* 5. Return the list of experts who know the secret.
*/
import java.util.*;
import java.util.stream.Collectors;
public class SecretSharingStream {
public List<Integer> findAllExperts(int n, int[][] meetings, int firstPerson) {
Set<Integer> secretHolders = new HashSet<>();
secretHolders.add(0);
secretHolders.add(firstPerson);
Arrays.stream(meetings)
.sorted(Comparator.comparingInt(m -> m[2]))
.forEach(meeting -> {
if (secretHolders.contains(meeting[0]) || secretHolders.contains(meeting[1])) {
secretHolders.add(meeting[0]);
secretHolders.add(meeting[1]);
}
});
return new ArrayList<>(secretHolders);
}
}
解释
方法:
此题解利用了图的广度优先搜索(BFS)的变体来传递信息。首先,创建一个图G,其中每个节点表示一个专家,边则代表两个专家在特定时间的会面。图中每个节点连接到的边带有时间标签,这样可以确保只有在正确的时间,专家才能互相分享秘密。初始化一个队列q,其中包含初始知道秘密的专家0和firstPerson。使用一个数组dis来记录每个专家最早知道秘密的时间。在遍历的过程中,如果当前专家在会议时间之前已经知道秘密,并且这个会议时间早于或等于目标专家的已知时间,则更新目标专家的已知时间并将其加入队列。最终,遍历dis数组,将所有不是无穷大的索引(代表这些专家知道了秘密)收集起来返回。
时间复杂度:
O(m)
空间复杂度:
O(m + n)
代码细节讲解
🦆
在构建图G时,为什么选择使用列表的列表而不是其他数据结构,例如哈希表或邻接矩阵?
▷🦆
在题解中使用了无穷大的值来初始化dis数组,这种方法在所有编程语言中都是通用的吗?如果不是,应该如何适应不同的编程环境?
▷