LeetCode 题解工作台
找出知晓秘密的所有专家
给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [x i , y i , time i ] 表示专家 x i 和专家 y i 在时间 time i 要开一场会。一个专家可以同时参加 …
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·DFS·traversal
答案摘要
本题的核心思路是通过模拟会议的传播过程来找出所有最终会知道秘密的人。我们可以将每次会议视为一个无向图的边，其中每个参与者是图中的一个节点，会议的时间是节点之间连接的边的“时间戳”。在每个时间点，我们遍历所有会议，利用广度优先搜索（BFS）来模拟秘密的传播。 创建一个布尔数组 来记录每个人是否知道秘密。初始时，$\textit{vis}[0] = \text{true}$ 和 $\textit{v…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。
专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。
秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。
在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。
示例 1：
输入：n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1 输出：[0,1,2,3,5] 解释： 时间 0 ，专家 0 将秘密与专家 1 共享。 时间 5 ，专家 1 将秘密与专家 2 共享。 时间 8 ，专家 2 将秘密与专家 3 共享。 时间 10 ，专家 1 将秘密与专家 5 共享。 因此，在所有会议结束后，专家 0、1、2、3 和 5 都将知晓这个秘密。
示例 2：
输入：n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3 输出：[0,1,3] 解释： 时间 0 ，专家 0 将秘密与专家 3 共享。 时间 2 ，专家 1 与专家 2 都不知晓这个秘密。 时间 3 ，专家 3 将秘密与专家 0 和专家 1 共享。 因此，在所有会议结束后，专家 0、1 和 3 都将知晓这个秘密。
示例 3：
输入：n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1 输出：[0,1,2,3,4] 解释： 时间 0 ，专家 0 将秘密与专家 1 共享。 时间 1 ，专家 1 将秘密与专家 2 共享，专家 2 将秘密与专家 3 共享。 注意，专家 2 可以在收到秘密的同一时间分享此秘密。 时间 2 ，专家 3 将秘密与专家 4 共享。 因此，在所有会议结束后，专家 0、1、2、3 和 4 都将知晓这个秘密。
提示：
2 <= n <= 1051 <= meetings.length <= 105meetings[i].length == 30 <= xi, yi <= n - 1xi != yi1 <= timei <= 1051 <= firstPerson <= n - 1
解题思路
方法一：模拟 + 图遍历
本题的核心思路是通过模拟会议的传播过程来找出所有最终会知道秘密的人。我们可以将每次会议视为一个无向图的边，其中每个参与者是图中的一个节点，会议的时间是节点之间连接的边的“时间戳”。在每个时间点，我们遍历所有会议，利用广度优先搜索（BFS）来模拟秘密的传播。
创建一个布尔数组 来记录每个人是否知道秘密。初始时， 和 ，表示0号和 已经知道秘密。
我们首先按照每个会议的时间进行排序，以确保每次遍历时能够按照正确的顺序处理会议。
接下来，处理每一组相同时间的会议。对于每一组相同时间的会议（即 ），我们将它们视为同一时刻发生的事件。对于每个会议，记录参与者的关系，并将这些参与者加入一个集合中。
然后，我们利用 BFS 来传播秘密。对于当前时间点的所有参与者，如果其中有任何人已经知道秘密，我们将通过 BFS 遍历该参与者的相邻节点（即会议中的其他参与者），将他们标记为知道秘密。这个过程会继续传播，直到所有在这次会议中能够知道秘密的人都被更新。
当所有会议处理完毕后，遍历 数组，将所有知道秘密的人的编号加入结果列表并返回。
时间复杂度 ，空间复杂度 。其中 和 分别是会议数量和专家数量。
class Solution:
def findAllPeople(
self, n: int, meetings: List[List[int]], firstPerson: int
) -> List[int]:
vis = [False] * n
vis[0] = vis[firstPerson] = True
meetings.sort(key=lambda x: x[2])
i, m = 0, len(meetings)
while i < m:
j = i
while j + 1 < m and meetings[j + 1][2] == meetings[i][2]:
j += 1
s = set()
g = defaultdict(list)
for x, y, _ in meetings[i : j + 1]:
g[x].append(y)
g[y].append(x)
s.update([x, y])
q = deque([u for u in s if vis[u]])
while q:
u = q.popleft()
for v in g[u]:
if not vis[v]:
vis[v] = True
q.append(v)
i = j + 1
return [i for i, v in enumerate(vis) if v]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O( M \log M + N) |
| 空间 | O(M + N) |
面试官常问的追问
外企场景- question_mark
Notice meetings may occur simultaneously and affect multiple people instantly.
- question_mark
Check if depth-first search or union-find is suitable for propagating secrets efficiently.
- question_mark
Ask whether sorting by time is necessary to correctly model the order of secret spreading.
常见陷阱
外企场景- error
Failing to account for multiple meetings occurring at the same time, which can block secret propagation.
- error
Using breadth-first search without grouping by time, which may incorrectly spread secrets across timestamps.
- error
Neglecting to include person 0 and firstPerson as initial secret holders in the propagation process.
进阶变体
外企场景- arrow_right_alt
Return the earliest time each person learns the secret instead of just who knows it.
- arrow_right_alt
Handle cases where a person can refuse to share the secret in some meetings, introducing conditional propagation.
- arrow_right_alt
Allow meetings to have duration intervals, requiring continuous secret propagation modeling across overlapping meetings.