登录3433. 统计用户被提及情况
解法
思路和算法
由于事件发生顺序为时间戳递增顺序，因此应将数组 $\textit{events}$ 按时间戳升序排序，然后遍历数组 $\textit{events}$，根据每个事件更新用户的相应状态。由于相同时间戳的离线和上线事件在消息事件之前处理，因此当存在多个事件的时间戳相同时，离线事件应在消息事件之前。
由于消息事件的提及用户的情况包括提及给定集合的用户、提及所有用户和提及所有在线用户，因此需要判断消息事件发生时每个用户的在线状态，可以通过维护每个用户的最新在线起始时间判断每个用户的在线状态。创建长度为 $\textit{numberOfUsers}$ 的数组 $\textit{onlineTimes}$，其中 $\textit{onlineTimes}[i]$ 表示编号 $i$ 的用户的最新在线起始时间。由于初始时所有用户都处于在线状态且所有事件的时间戳都是正整数，因此将数组 $\textit{onlineTimes}$ 中的所有元素都初始化为 $0$。
创建长度为 $\textit{numberOfUsers}$ 的结果数组 $\textit{mentions}$。遍历排序后的数组 $\textit{events}$，对于遍历到的每个事件 $[\textit{type}, \textit{timestamp}, \textit{users}]$，判断其类型，执行相应的操作。
-
如果 $\textit{types} = \text{``MESSAGE"}$，则当前事件是消息事件，根据 $\textit{users}$ 的值决定需要提及的用户，执行提及操作。
-
当 $\textit{users} = \text{``ALL"}$ 时，提及所有用户，将数组 $\textit{mentions}$ 中的所有元素值都增加 $1$。
-
当 $\textit{users} = \text{``HERE"}$ 时，提及所有在线用户，遍历 $0 \le i < \textit{numberOfUsers}$ 的每个用户编号 $i$，如果 $\textit{onlineTimes}[i] \le \textit{timestamp}$，则编号 $i$ 的用户被提及，将 $\textit{mentions}[i]$ 的值增加 $1$。
-
其余情况下，将 $\textit{users}$ 使用空格分隔转换成数组，遍历数组中的每个用户编号，将用户编号对应的数组 $\textit{mentions}$ 中的元素值增加 $1$。
-
-
如果 $\textit{types} = \text{``OFFLINE"}$，则当前事件是离线事件，用 $\textit{id}$ 表示 $\textit{users}$ 对应的用户编号，则编号为 $\textit{id}$ 的用户在时间戳 $\textit{timestamp}$ 离线，并将在时间戳 $\textit{timestamp} + 60$ 自动上线，因此将 $\textit{onlineTimes}[\textit{id}]$ 的值更新为 $\textit{timestamp} + 60$。
遍历结束之后，结果数组 $\textit{mentions}$ 即为每个用户被提及的次数。
代码
###Java
class Solution {
static final String MESSAGE = "MESSAGE", OFFLINE = "OFFLINE", ALL = "ALL", HERE = "HERE";
static final int OFFLINE_TIME = 60;
public int[] countMentions(int numberOfUsers, List<List<String>> events) {
Collections.sort(events, (a, b) -> {
int aTimestamp = Integer.parseInt(a.get(1)), bTimestamp = Integer.parseInt(b.get(1));
if (aTimestamp != bTimestamp) {
return aTimestamp - bTimestamp;
} else {
String aType = a.get(0), bType = b.get(0);
return bType.compareTo(aType);
}
});
int[] mentions = new int[numberOfUsers];
int[] onlineTimes = new int[numberOfUsers];
for (List<String> ev : events) {
String type = ev.get(0);
int timestamp = Integer.parseInt(ev.get(1));
String users = ev.get(2);
if (MESSAGE.equals(type)) {
if (ALL.equals(users)) {
updateMentions(mentions, onlineTimes, Integer.MAX_VALUE);
} else if (HERE.equals(users)) {
updateMentions(mentions, onlineTimes, timestamp);
} else {
String[] ids = users.split(" ");
for (String idStr : ids) {
int id = Integer.parseInt(idStr.substring(2));
mentions[id]++;
}
}
} else {
int id = Integer.parseInt(users);
onlineTimes[id] = timestamp + OFFLINE_TIME;
}
}
return mentions;
}
public void updateMentions(int[] mentions, int[] onlineTimes, int timestamp) {
int numberOfUsers = mentions.length;
for (int i = 0; i < numberOfUsers; i++) {
if (onlineTimes[i] <= timestamp) {
mentions[i]++;
}
}
}
}
###C#
public class Solution {
const string MESSAGE = "MESSAGE", OFFLINE = "OFFLINE", ALL = "ALL", HERE = "HERE";
const int OFFLINE_TIME = 60;
public int[] CountMentions(int numberOfUsers, IList<IList<string>> events) {
((List<IList<string>>) events).Sort((a, b) => {
int aTimestamp = int.Parse(a[1]), bTimestamp = int.Parse(b[1]);
if (aTimestamp != bTimestamp) {
return aTimestamp - bTimestamp;
} else {
string aType = a[0], bType = b[0];
return bType.CompareTo(aType);
}
});
int[] mentions = new int[numberOfUsers];
int[] onlineTimes = new int[numberOfUsers];
foreach (IList<string> ev in events) {
string type = ev[0];
int timestamp = int.Parse(ev[1]);
string users = ev[2];
if (MESSAGE.Equals(type)) {
if (ALL.Equals(users)) {
UpdateMentions(mentions, onlineTimes, int.MaxValue);
} else if (HERE.Equals(users)) {
UpdateMentions(mentions, onlineTimes, timestamp);
} else {
string[] ids = users.Split(" ");
foreach (string idStr in ids) {
int id = int.Parse(idStr.Substring(2));
mentions[id]++;
}
}
} else {
int id = int.Parse(users);
onlineTimes[id] = timestamp + OFFLINE_TIME;
}
}
return mentions;
}
public void UpdateMentions(int[] mentions, int[] onlineTimes, int timestamp) {
int numberOfUsers = mentions.Length;
for (int i = 0; i < numberOfUsers; i++) {
if (onlineTimes[i] <= timestamp) {
mentions[i]++;
}
}
}
}
复杂度分析
-
时间复杂度：$O(n \log n \log t + \textit{numberOfUsers} + L)$，其中 $n$ 是数组 $\textit{events}$ 的长度，$\textit{numberOfUsers}$ 是用户总数，$t$ 是数组 $\textit{events}$ 中的时间戳最大值，$L$ 是数组 $\textit{events}$ 中的所有提及字符串的长度之和。将数组 $\textit{events}$ 排序的时间是 $O(n \log n \log t)$，创建数组 $\textit{mentions}$ 和 $\textit{onlineTimes}$ 的时间是 $O(\textit{numberOfUsers})$，遍历排序后的数组 $\textit{events}$ 计算提及次数的时间是 $O(n + L)$，因此时间复杂度是 $O(n \log n \log t + \textit{numberOfUsers} + L)$。
-
空间复杂度：$O(n + \textit{numberOfUsers})$，其中 $n$ 是数组 $\textit{events}$ 的长度，$\textit{numberOfUsers}$ 是用户总数。由于待排序的元素是数组，因此排序的空间是 $O(n)$，记录每个用户的最新在线起始时间的空间是 $O(\textit{numberOfUsers})$。
