Medium
题目描述
给定一个整数 numberOfUsers 表示用户总数，以及一个大小为 n x 3 的数组 events。
每个 events[i] 可以是以下两种类型之一：
消息事件：["MESSAGE", "timestampi", "mentions_stringi"]
- 这个事件表示在时间戳
timestampi的一条消息中提及了一组用户 mentions_stringi字符串可以包含以下令牌之一：id<number>：其中<number>是范围[0, numberOfUsers - 1]内的整数。可以有多个由单个空格分隔的 id，并且可能包含重复项。这甚至可以提及离线用户ALL：提及所有用户HERE：提及所有在线用户
离线事件：["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]
示例 2：
输入：numberOfUsers = 2, events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","12","ALL"]]
输出：[2,2]
示例 3：
输入：numberOfUsers = 2, events = [["OFFLINE","10","0"],["MESSAGE","12","HERE"]]
输出：[0,1]
约束：
1 <= numberOfUsers <= 1001 <= events.length <= 100events[i].length == 3events[i][0]将是MESSAGE或OFFLINE之一1 <= int(events[i][1]) <= 10^5- 任何 “MESSAGE” 事件中的
id<number>提及次数在 1 到 100 之间 0 <= <number> <= numberOfUsers - 1- 保证 OFFLINE 事件中引用的用户 id 在事件发生时是在线的
解题思路
解题思路
这道题需要模拟用户的在线/离线状态变化和消息提及处理过程。
核心思路：
- 状态管理：维护每个用户的在线状态，所有用户初始在线
- 时间排序：按时间戳对事件排序，确保按时间顺序处理
- 状态更新：处理离线事件时，记录用户离线时间，并在合适时机自动恢复在线
- 消息处理：根据提及类型（具体 id、ALL、HERE）统计每个用户的被提及次数
具体步骤：
- 首先按时间戳排序所有事件
- 对每个时间戳，先处理所有用户的状态变化（离线恢复、新离线）
- 然后处理该时间戳的消息事件
- 对于消息中的提及：
id<number>：直接统计对应用户ALL：统计所有用户（包括离线用户）HERE：只统计当前在线用户
关键细节：
- 用户离线 60 个时间单位后自动上线
- 同一时间戳先处理状态变化，再处理消息
- 重复提及需要分别计算
代码实现
class Solution {
public:
vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
// 按时间戳排序事件
sort(events.begin(), events.end(), [](const vector<string>& a, const vector<string>& b) {
return stoi(a[1]) < stoi(b[1]);
});
vector<int> mentions(numberOfUsers, 0);
vector<int> offlineUntil(numberOfUsers, -1); // -1表示在线
for (const auto& event : events) {
int timestamp = stoi(event[1]);
// 更新用户在线状态
for (int i = 0; i < numberOfUsers; i++) {
if (offlineUntil[i] != -1 && timestamp >= offlineUntil[i]) {
offlineUntil[i] = -1; // 重新上线
}
}
if (event[0] == "OFFLINE") {
int userId = stoi(event[2]);
offlineUntil[userId] = timestamp + 60;
} else { // MESSAGE
string mentionStr = event[2];
if (mentionStr == "ALL") {
for (int i = 0; i < numberOfUsers; i++) {
mentions[i]++;
}
} else if (mentionStr == "HERE") {
for (int i = 0; i < numberOfUsers; i++) {
if (offlineUntil[i] == -1) { // 在线用户
mentions[i]++;
}
}
} else {
// 解析id列表
stringstream ss(mentionStr);
string token;
while (ss >> token) {
if (token.substr(0, 2) == "id") {
int userId = stoi(token.substr(2));
mentions[userId]++;
}
}
}
}
}
return mentions;
}
};
class Solution:
def countMentions(self, numberOfUsers: int, events: List[List[str]]) -> List[int]:
# 按时间戳排序事件
events.sort(key=lambda x: int(x[1]))
mentions = [0] * numberOfUsers
offline_until = [-1] * numberOfUsers # -1表示在线
for event in events:
timestamp = int(event[1])
# 更新用户在线状态
for i in range(numberOfUsers):
if offline_until[i] != -1 and timestamp >= offline_until[i]:
offline_until[i] = -1 # 重新上线
if event[0] == "OFFLINE":
user_id = int(event[2])
offline_until[user_id] = timestamp + 60
else: # MESSAGE
mention_str = event[2]
if mention_str == "ALL":
for i in range(numberOfUsers):
mentions[i] += 1
elif mention_str == "HERE":
for i in range(numberOfUsers):
if offline_until[i] == -1: # 在线用户
mentions[i] += 1
else:
# 解析id列表
tokens = mention_str.split()
for token in tokens:
if token.startswith("id"):
user_id = int(token[2:])
mentions[user_id] += 1
return mentions
public class Solution {
public int[] CountMentions(int numberOfUsers, IList<IList<string>> events) {
// 转换并按时间戳排序事件
var eventList = events.ToList();
eventList.Sort((a, b) => int.Parse(a[1]).CompareTo(int.Parse(b[1])));
int[] mentions = new int[numberOfUsers];
int[] offlineUntil = new int[numberOfUsers];
Array.Fill(offlineUntil, -1); // -1表示在线
foreach (var eventItem in eventList) {
int timestamp = int.Parse(eventItem[1]);
// 更新用户在线状态
for (int i = 0; i < numberOfUsers; i++) {
if (offlineUntil[i] != -1 && timestamp >= offlineUntil[i]) {
offlineUntil[i] = -1; // 重新上线
}
}
if (eventItem[0] == "OFFLINE") {
int userId = int.Parse(eventItem[2]);
offlineUntil[userId] = timestamp + 60;
} else { // MESSAGE
string mentionStr = eventItem[2];
if (mentionStr == "ALL") {
for (int i = 0; i < numberOfUsers; i++) {
mentions[i]++;
}
} else if (mentionStr == "HERE") {
for (int i = 0; i < numberOfUsers; i++) {
if (offlineUntil[i] == -1) { // 在线用户
mentions[i]++;
}
}
} else {
// 解析id列表
string[] tokens = mentionStr.Split(' ');
foreach (string token in tokens) {
if (token.StartsWith("id")) {
int userId = int.Parse(token.Substring(2));
mentions[userId]++;
}
}
}
}
}
return mentions;
}
}
var countMentions = function(numberOfUsers, events) {
// 按时间戳排序事件
events.sort((a, b) => parseInt(a[1]) - parseInt(b[1]));
const mentions = new Array(numberOfUsers).fill(0);
const offlineUntil = new Array(numberOfUsers).fill(-1); // -1表示在线
for (const event of events) {
const timestamp = parseInt(event[1]);
// 更新用户在线状态
for (let i = 0; i < numberOfUsers; i++) {
if (offlineUntil[i] !== -1 && timestamp >= offlineUntil[i]) {
offlineUntil[i] = -1; // 重新上线
}
}
if (event[0]
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(E log E + E × N + M) |
| 空间复杂度 | O(N) |
其中：
- E 是事件数量
- N 是用户数量
- M 是所有消息事件中的总提及数量
- 排序时间复杂度为 O(E log E)
- 每个事件处理时间为 O(N)（更新状态）+ O(提及数量)
- 空间复杂度主要用于存储用户状态和结果数组