leetcode
leetcode 1851 ~ 1900
找出知晓秘密的所有专家

找出知晓秘密的所有专家

难度:

标签:

题目描述

代码结果

运行时间: 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时,为什么选择使用列表的列表而不是其他数据结构,例如哈希表或邻接矩阵?
在构建图G时选择使用列表的列表(即邻接表)主要基于存储效率和访问速度的考虑。对于稀疏图,即边的数目远小于顶点数的平方,邻接表比邻接矩阵更节省空间,因为它只需要存储存在的边。此外,使用邻接表可以更快地遍历一个顶点的所有邻接点,这在BFS中非常有用,因为我们通常需要快速访问一个顶点的所有邻接顶点。而使用哈希表虽然也可以实现类似的结构,但在这种情况下增加了不必要的复杂度和可能的性能开销,因为列表已经足够满足需求。
🦆
在题解中使用了无穷大的值来初始化dis数组,这种方法在所有编程语言中都是通用的吗?如果不是,应该如何适应不同的编程环境?
在题解中使用无穷大的值(如0xffffff)来初始化dis数组是为了标记那些还未知晓秘密的专家。这种方法并非在所有编程语言中都是通用的,不同的编程语言和环境可能需要不同的方式来表示足够大的数值。在一些语言中,可能直接有表示无穷大的内置值(如Python中的float('inf')),而在其他如C或Java中,可能需要使用最大整数值MAX_INT来近似。在实现时,应选择该语言中表示极大数值的标准方式,或者根据问题的具体需求选择一个足够大的数值,以确保它不会被任何有效的时间戳覆盖。

相关问题