聊天日志次数TopK：计事件与不同联系人分开

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练messages每条是发送者ID，一条已接受事件算一次。若题中双方都计次数需改聚合。
• ID可排序，exact K并列按ID最小；k超过人数返回全部。重复传输是否同事件需上游ID去重。

解题路线

1. Counter聚合后全排序按(−count,id)，得到确定TopK。这是K可变查询的可靠基线，不能用不同邻居set替代次数。
2. 小K可维护大小K最小堆O(UlogK)，quickselect均摊O(U)后还要处理边界tie及结果排序；全排序适合需连续多个K的静态快照。
3. 流式实时维护次数时更新频繁，可版本heap/O(logU)有序排名树；普通heap不支持直接改键，不能改元素却不恢复堆性质。

手动走一遍

发送者[A,A,B]，A次数2、B1；即使A总找同一个人，其消息次数仍2。A/B各2且k1，按约定取较小ID；若要求全部并列，则结果长度会>k。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import Counter

def top_users(messages,k):
    # Each record is the sender ID of one accepted chat event.
    if k<0:raise ValueError("nonnegative k")
    counts=Counter(messages)
    return sorted(counts,key=lambda user:(-counts[user],user))[:k]

复杂度

N日志/U用户，基线O(N+UlogU)时间/O(U)空间；读取流本身无需全部保留。

易错点与追问

容易失分的边界

• 对不同联系人计数是另一道活跃用户题。
• 去重同用户全部记录会把频次消掉。

继续深挖

• 有限内存时如何外部分区聚合，再全局TopK？
• 时间窗口内次数需怎样过期，乱序事件如何处理？