LeetCode 题解工作台
统计用户被提及情况
给你一个整数 numberOfUsers 表示用户总数，另有一个大小为 n x 3 的数组 events 。 每个 events[i] 都属于下述两种类型之一： 消息事件（Message Event）： ["MESSAGE", "timestamp i ", "mentions_string i "…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
我们将事件按照时间戳升序排序，如果时间戳相同，我们将 OFFLINE 事件排在 MESSAGE 事件之前。 然后我们模拟事件的发生过程，使用 `online_t` 数组记录每个用户下一次上线的时间，用一个变量 `lazy` 记录所有用户还需要被提及的次数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个整数 numberOfUsers 表示用户总数，另有一个大小为 n x 3 的数组 events 。
每个 events[i] 都属于下述两种类型之一：
- 消息事件（Message Event）：
["MESSAGE", "timestampi", "mentions_stringi"]- 事件表示在
timestampi时，一组用户被消息提及。 mentions_stringi字符串包含下述标识符之一：id<number>：其中<number>是一个区间[0,numberOfUsers - 1]内的整数。可以用单个空格分隔 多个 id ，并且 id 可能重复。此外，这种形式可以提及离线用户。ALL：提及 所有 用户。HERE：提及所有 在线 用户。
- 事件表示在
- 离线事件（Offline Event）：
["OFFLINE", "timestampi", "idi"]- 事件表示用户
idi在timestampi时变为离线状态 60 个单位时间。用户会在timestampi + 60时自动再次上线。
- 事件表示用户
返回数组 mentions ，其中 mentions[i] 表示 id 为 i 的用户在所有 MESSAGE 事件中被提及的次数。
最初所有用户都处于在线状态，并且如果某个用户离线或者重新上线，其对应的状态变更将会在所有相同时间发生的消息事件之前进行处理和同步。
注意 在单条消息中，同一个用户可能会被提及多次。每次提及都需要被 分别 统计。
示例 1：
输入：numberOfUsers = 2, events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","71","HERE"]]
输出：[2,2]
解释：
最初，所有用户都在线。
时间戳 10 ，id1 和 id0 被提及，mentions = [1,1]
时间戳 11 ，id0 离线 。
时间戳 71 ，id0 再次 上线 并且 "HERE" 被提及，mentions = [2,2]
示例 2：
输入：numberOfUsers = 2, events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","12","ALL"]]
输出：[2,2]
解释：
最初，所有用户都在线。
时间戳 10 ，id1 和 id0 被提及，mentions = [1,1]
时间戳 11 ，id0 离线 。
时间戳 12 ，"ALL" 被提及。这种方式将会包括所有离线用户，所以 id0 和 id1 都被提及，mentions = [2,2]
示例 3：
输入：numberOfUsers = 2, events = [["OFFLINE","10","0"],["MESSAGE","12","HERE"]]
输出：[0,1]
解释：
最初，所有用户都在线。
时间戳 10 ，id0 离线 。
时间戳 12 ，"HERE" 被提及。由于 id0 仍处于离线状态，其将不会被提及，mentions = [0,1]
提示：
1 <= numberOfUsers <= 1001 <= events.length <= 100events[i].length == 3events[i][0]的值为MESSAGE或OFFLINE。1 <= int(events[i][1]) <= 105- 在任意
"MESSAGE"事件中，以id<number>形式提及的用户数目介于1和100之间。 0 <= <number> <= numberOfUsers - 1- 题目保证
OFFLINE引用的用户 id 在事件发生时处于 在线 状态。
解题思路
方法一：排序 + 模拟
我们将事件按照时间戳升序排序，如果时间戳相同，我们将 OFFLINE 事件排在 MESSAGE 事件之前。
然后我们模拟事件的发生过程，使用 online_t 数组记录每个用户下一次上线的时间，用一个变量 lazy 记录所有用户还需要被提及的次数。
遍历事件列表，根据事件类型进行处理：
- 如果是 ONLINE 事件，我们更新
online_t数组； - 如果是 ALL 事件，我们将
lazy加一； - 如果是 HERE 事件，我们遍历
online_t数组，如果用户下一次上线的时间小于等于当前时间，我们将该用户的提及次数加一； - 如果是 MESSAGE 事件，我们将提及的用户的提及次数加一。
最后，如果 lazy 大于 0，我们将所有用户的提及次数加上 lazy。
时间复杂度 ，空间复杂度 。其中 和 分别是用户总数和事件总数，而 和 分别是时间戳的最大值以及所有提及的字符串的总长度。
class Solution:
def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
events.sort(key=lambda e: (int(e[1]), e[0][2]))
ans = [0] * numberOfUsers
online_t = [0] * numberOfUsers
lazy = 0
for etype, ts, s in events:
cur = int(ts)
if etype[0] == "O":
online_t[int(s)] = cur + 60
elif s[0] == "A":
lazy += 1
elif s[0] == "H":
for i, t in enumerate(online_t):
if t <= cur:
ans[i] += 1
else:
for a in s.split():
ans[int(a[2:])] += 1
if lazy:
for i in range(numberOfUsers):
ans[i] += lazy
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * m) where n is the number of events and m is the number of user mentions per MESSAGE, due to iterating over users in messages. Sorting events by timestamp adds O(n log n). Space complexity is O(u) for arrays tracking online status and mention counts, where u is numberOfUsers. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Mentions array should correctly reflect online filtering.
- question_mark
Sorting events before processing is a key optimization hint.
- question_mark
Handle special keywords like ALL carefully to avoid miscounting.
常见陷阱
外企场景- error
Counting offline users during normal MESSAGE events.
- error
Failing to sort events by timestamp before processing.
- error
Incorrectly indexing users when mapping id strings to array positions.
进阶变体
外企场景- arrow_right_alt
MESSAGE events could include additional special keywords beyond ALL.
- arrow_right_alt
Users might toggle between online and offline multiple times per test case.
- arrow_right_alt
Events could arrive unsorted or with duplicate timestamps requiring stable processing.