短信活跃用户：不同邻居去重、O(1)冠军与TopK

题意与假设

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

• 用户ID采用整数以定义稳定并列规则；不接受自消息。register只添加，不删除关系。
• 活跃度=不同其他用户数；most_active并列取ID最小；top_k返回至多K人。

解题路线

1. 邻接set将重复register幂等化。每条新关系只可能改变两端度数，其他人的排名不变。
2. 保存当前冠军。每次更新端点，用(度数大、ID小)与冠军比较；加边不会使冠军分数下降，所以检查这两人足够。
3. TopK基线用固定大小堆O(UlogK)，K可变时每次扫描查询即可。频繁任意K查询需维护有序排名树，以(−degree,ID)为键，更新端点删除旧键插新键，按序取K。

手动走一遍

register(2,3),register(1,2)：2有两邻居，1和3各一；再次register(1,2)冠军仍2，度数不增加。仅(2,3)时冠军2，因为度数同为1按最小ID取。

Python 参考实现

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

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

from heapq import nlargest


class Activity:
    def __init__(self):
        self.neighbors = {}
        self.leader = None

    def register(self, a, b):
        if a == b:
            raise ValueError("no self messages")
        for u, v in ((a,b),(b,a)):
            self.neighbors.setdefault(u,set()).add(v)
            if self.leader is None or len(self.neighbors[u]) > len(self.neighbors[self.leader]) or (len(self.neighbors[u]) == len(self.neighbors[self.leader]) and u < self.leader):
                self.leader = u

    def most_active(self):
        return self.leader

    def top_k(self, k):
        if k < 0:
            raise ValueError("nonnegative k required")
        return nlargest(k, self.neighbors, key=lambda u:(len(self.neighbors[u]),-u))

复杂度

register期望O(1)、most_active O(1)，邻接空间O(U+E)，稠密图E=Θ(U²)。nlargest查询通常O(Ulogmin(K,U))，K≥U可排序O(UlogU)。

易错点与追问

容易失分的边界

• 把消息次数当度数会偏向重复聊天。
• 删除边可能降低冠军，缓存最大值不再可直接维持。

继续深挖

• 允许delete时如何维护有序树或带版本lazyheap？
• TopK含全部并列时，返回元素数为何可能远超过K？