3433. 统计用户被提及情况

作者

🚀 算法笔记：消息提及计数 (Count Mentions)

1. 题目逻辑核心

本题是一个典型的时间序列模拟问题。其核心挑战在于处理事件的顺序性与原子状态更新。

核心解题策略

  • 离线处理：预先获取所有事件并进行全局排序，构建统一的时间线。

  • 优先级排序 (Tie-breaking)：在同一时刻，状态变更（下线）必须发生在行为判定（发消息）之前。

2. 算法实现分析

A. 事件排序逻辑 (Sorting Criteria)

排序是程序的灵魂，决定了模拟的正确性。

优先级 关键属性 排序规则 原因
1 timestamp 升序 严格遵循时间流逝顺序
2 type OFFLINE 优先 确保 $t$ 时刻下线的人在 $t$ 时刻的 @HERE 统计中被视为“不可见”
C++

// 排序实现代码片段
sort(events.begin(), events.end(), [](const vector<string>& a, const vector<string>& b) {
    int timeA = stoi(a[1]), timeB = stoi(b[1]);
    if (timeA == timeB) return a[0] == "OFFLINE"; // OFFLINE 优先
    return timeA < timeB;
});

B. 状态机设计 (State Management)

与其使用 bool 记录状态并开启定时器，不如记录 “解禁时间点”。

  • online_time[i]：存储用户 $i$ 重新变为 ONLINE 的时间戳。

  • 状态转移逻辑：

    • 下线：online_time[userId] = timestamp + 60。

    • 判定：current_time >= online_time[userId] $\Rightarrow$ 此时用户是在线的。

C. 消息类型解析 (Dispatching)

  1. ALL：全员 $O(K)$ 累加。

  2. HERE：根据 online_time 过滤在线用户。

  3. id<num>：精准解析。利用 token.substr(2) 剥离前缀，高效转换。

3. C++ 高级语法点复习

std::stringstream

它是处理变长、空格分隔字符串的利器。相比于手动 find 空格，ss >> token 更加安全且易读。

Lambda 表达式

在 sort 中直接定义闭包，避免了外部静态函数的定义，使代码更加内聚。

4. 复杂度深度评估

维度 复杂度 (Big O) 关键因素
时间复杂度 $O(N \log N + M \cdot K)$ $N$=事件数, $M$=消息事件数, $K$=用户总数
空间复杂度 $O(K)$ 需要存储 ans 和 online_time 两个辅助数组

💡 潜在优化与进阶思考

  1. 性能瓶颈：当 $K$（用户数）极大时，处理 ALL 消息的 $O(K)$ 循环会成为性能灾难。

    • 优化建议：引入一个全局变量 totalAllMentions。当收到 ALL 消息时只更新全局变量，最后结算时合并到每个用户的 ans 中。

  2. 字符串性能：stoi 和 stringstream 涉及频繁的内存分配。

    • 优化建议：对于性能敏感场景，可改用 std::from_chars（C++17）进行极致的数值转换。

示例代码 (整理版)

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>

using namespace std;

class Solution {
public:
    vector<int> countMentions(int numberOfUsers, vector<vector<string>>& events) {
        // 1. 离线排序：时间优先，同时间下线优先
        sort(events.begin(), events.end(), [](const vector<string>& a, const vector<string>& b) {
            int t1 = stoi(a[1]), t2 = stoi(b[1]);
            return t1 == t2 ? a[0] == "OFFLINE" : t1 < t2;
        });

        vector<int> online_time(numberOfUsers, 0);
        vector<int> ans(numberOfUsers, 0);

        // 2. 模拟事件流
        for (const auto& e : events) {
            int ts = stoi(e[1]);
            if (e[0] == "OFFLINE") {
                online_time[stoi(e[2])] = ts + 60;
            } else {
                if (e[2] == "ALL") {
                    for (int i = 0; i < numberOfUsers; ++i) ans[i]++;
                } else if (e[2] == "HERE") {
                    for (int i = 0; i < numberOfUsers; ++i) {
                        if (ts >= online_time[i]) ans[i]++;
                    }
                } else {
                    stringstream ss(e[2]);
                    string token;
                    while (ss >> token) ans[stoi(token.substr(2))]++;
                }
            }
        }
        return ans;
    }
};

发表评论