2025-08-04：统计用户被提及情况。用go语言，你有一个整数 numberOfUsers，表示用户总数量，还有一个大小为 n x 3 的二维数组 events。

每个 events[i] 代表两种事件之一：

  1. 消息事件（MESSAGE）：格式为 ["MESSAGE", "timestamp", "mentions_string"]

    • 表示在 timestamp 时间点，有一条消息提到了若干用户。

    • mentions_string 可能是以下形式之一：

      • 多个用户 ID，用空格分隔，如 id<number>，其中 <number> 是 0 到 numberOfUsers - 1 的整数，且可能有重复，也可以包含离线用户。

      • "ALL"：代表提及所有用户。

      • "HERE"：代表提及所有当前在线的用户。

  2. 离线事件（OFFLINE）：格式为 ["OFFLINE", "timestamp", "id"]

    • 表示用户 id 在 timestamp 时间点进入离线状态，持续 60 单位时间，之后（timestamp + 60）会自动恢复在线。

初始状态下所有用户都是在线的。如果多个事件时间相同，状态变化（离线或恢复）会先于消息事件处理并生效。

最终你需要返回一个长度为 numberOfUsers 的数组 mentions，其中 mentions[i] 是用户 i 在所有消息事件中被提及的总次数。

特别注意，单条消息中同一个用户被多次提及，需要累计每次提及的次数。

1 <= numberOfUsers <= 100。

1 <= events.length <= 100。

events[i].length == 3。

events[i][0] 的值为 MESSAGE 或 OFFLINE 。

1 <= int(events[i][1]) <= 100000。

在任意 "MESSAGE" 事件中，以 id<number> 形式提及的用户数目介于 1 和 100 之间。

0 <= <number> <= numberOfUsers - 1。

题目保证 OFFLINE 引用的用户 id 在事件发生时处于 在线 状态。

输入：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]。

题目来自力扣3433。

分步骤描述过程

  1. 事件排序：

    • 首先，对所有事件按照时间戳（events[i][1]）进行升序排序（从小到大）。
    • 如果两个事件的时间戳相同，则优先处理离线事件（OFFLINE），再处理消息事件（MESSAGE）。这是因为题目要求状态变化（如离线）先于消息事件生效。排序规则确保在相同时间戳下，OFFLINE 事件排在 MESSAGE 事件之前。

  2. 初始化数据结构：

    • 创建一个长度 numberOfUsers 的结果数组 ans，初始化为全 0，用于存储每个用户被提及的总次数。
    • 创建一个长度 numberOfUsers 的数组 onlineT，初始化为全 0。onlineT[i] 表示用户 i 下一次恢复在线的时间戳。初始值为 0 表示所有用户在线（因为时间戳从 1 开始，任何时间点 t ≥ 1 > 0 都满足在线条件）。

  3. 遍历处理事件：

    • 按排序后的事件顺序依次处理每个事件。
    • 提取当前事件的时间戳 curT（将 events[i][1] 转换为整数）。
    • 根据事件类型执行不同操作：
      • OFFLINE 事件：
        • 格式：["OFFLINE", timestamp, id]，其中 id 是直接的数字字符串（如 "0"）。
        • 将 id 转换为整数 i（表示用户索引）。
        • 设置 onlineT[i] = curT + 60，表示用户 i 将在 curT + 60 时间点恢复在线。
      • MESSAGE 事件：
        • 格式：["MESSAGE", timestamp, mentions_string]。
        • 根据 mentions_string 的内容处理提及：
          • "ALL"：表示提及所有用户。
            • 遍历所有用户索引 i（0 到 numberOfUsers - 1），将 ans[i] 加 1。
          • "HERE"：表示提及所有当前在线用户。
            • 遍历所有用户索引 i，检查 onlineT[i] <= curT（如果为真，表示用户在线）。
            • 对在线的用户，将 ans[i] 加 1。
          • 用户 ID 列表：格式为空格分隔的 "id<number>" 字符串（如 "id1 id0"）。
            • 使用空格分割 mentions_string 得到多个子串（如 ["id1", "id0"]）。
            • 对每个子串：
              • 提取数字部分（去除前缀 "id"，即取子串 s[2:]）。
              • 将数字字符串转换为整数 i（表示用户索引）。
              • 将 ans[i] 加 1。
            • 注意：同一用户可能在单条消息中被多次提及（如 "id0 id0"），每次提及都会独立计数。

  4. 在线状态管理：

    • 通过 onlineT 数组隐式管理用户在线状态：
      • 用户 i 在时间 t 在线当且仅当 onlineT[i] <= t。
      • 离线事件（OFFLINE）设置 onlineT[i] = curT + 60，表示从 curT 到 curT + 60 - 1 用户离线，在 curT + 60 及之后自动恢复在线。
    • 在消息事件中（尤其是 "HERE"）直接使用 curT 与 onlineT[i] 比较判断在线状态，无需显式处理恢复事件。

  5. 处理重复提及和边界：

    • 单条消息中同一用户多次提及会被多次计数（如 "id0 id0" 会使 ans[0] 增加 2）。
    • 题目保证 OFFLINE 事件发生时用户在线，因此设置 onlineT[i] 是安全的。
    • 时间戳相同时，排序确保 OFFLINE 先执行，状态更新后 MESSAGE 才使用新状态。

时间复杂度和空间复杂度

  • 时间复杂度：
    • 排序事件：使用快速排序（slices.SortFunc），时间复杂度为 O(n log n)，其中 n 是事件数量（events.length ≤ 100）。
    • 处理事件：遍历 n 个事件。
      • OFFLINE 事件：处理时间为 O(1)。
      • MESSAGE 事件：
        • "ALL" 或 "HERE"：遍历 m 个用户（m = numberOfUsers ≤ 100），时间为 O(m)。
        • 用户 ID 列表：处理时间 O(k)，其中 k 是提及的用户数量（k ≤ 100）。
      • 最坏情况下，所有事件都是 "ALL" 或 "HERE"，总时间为 **O(n * m)**。
    • 整体时间复杂度：O(n log n + n * m)。由于 n ≤ 100，m ≤ 100，实际可视为常数时间（约 100 × log₂100 + 100 × 100 ≈ 700 + 10000 = 10700 操作）。
  • 空间复杂度：
    • 存储结果数组 ans 和在线时间数组 onlineT：各占用 O(m) 空间。
    • 排序使用原地排序，栈空间 O(log n)。
    • 处理用户 ID 列表时临时分割字符串：占用 O(k) 临时空间（k ≤ 100）。
    • 总体额外空间复杂度：O(m)（m = numberOfUsers ≤ 100），即线性于用户数量。

Go完整代码如下：

package mainimport ("fmt""strconv""strings""cmp""slices"
)func countMentions(numberOfUsers int, events [][]string) []int {// 按照时间戳从小到大排序，时间戳相同的，离线事件排在前面slices.SortFunc(events, func(a, b []string) int {ta, _ := strconv.Atoi(a[1])tb, _ := strconv.Atoi(b[1])return cmp.Or(ta-tb, int(b[0][0])-int(a[0][0]))})ans := make([]int, numberOfUsers)onlineT := make([]int, numberOfUsers)for _, e := range events {curT, _ := strconv.Atoi(e[1])if e[0][0] == 'O' {i, _ := strconv.Atoi(e[2])onlineT[i] = curT + 60} else if e[2][0] == 'A' {for i := range ans {ans[i]++}} else if e[2][0] == 'H' {for i, t := range onlineT {if t <= curT { // 在线ans[i]++}}} else {for _, s := range strings.Split(e[2], " ") {i, _ := strconv.Atoi(s[2:])ans[i]++}}}return ans
}func main() {numberOfUsers := 2events := [][]string{{"MESSAGE","10","id1 id0"},{"OFFLINE","11","0"},{"MESSAGE","71","HERE"}}result := countMentions(numberOfUsers,events)fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

# -*-coding:utf-8-*-def count_mentions(numberOfUsers, events):# 排序事件：首先按时间戳升序，时间戳相同时，按事件类型首字母的ASCII值降序（即离线事件在前）events.sort(key=lambda e: (int(e[1]), -ord(e[0][0])))ans = [0] * numberOfUsersonlineT = [0] * numberOfUsers  # 记录每个用户被视为在线的截止时间戳for e in events:curT = int(e[1])if e[0] == "OFFLINE":user_id = int(e[2])onlineT[user_id] = curT + 60elif e[0] == "MESSAGE":content = e[2]if content.startswith('A'):  # 全体消息for i in range(numberOfUsers):ans[i] += 1elif content.startswith('H'):  # 在线消息for i in range(numberOfUsers):# 注意：这里条件与Go代码一致（onlineT[i] <= curT 表示用户在线）if onlineT[i] <= curT:ans[i] += 1else:  # 定向消息parts = content.split()for part in parts:# 提取"idX"中的X并转换为整数user_id = int(part[2:])ans[user_id] += 1return ansdef main():numberOfUsers = 2events = [["MESSAGE","10","id1 id0"],["OFFLINE","11","0"],["MESSAGE","71","HERE"]]result = count_mentions(numberOfUsers, events)print(result)if __name__ == "__main__":main()

在这里插入图片描述