algorithm - 有效率的时间记分牌？

Question

我想维护一个记分牌，其中包含根据分数排序的 n 个玩家，我所做的是:当玩家 i 获得 x 分时(如果他还不是最高玩家)，我将他的分数与他上面玩家的分数进行比较，以便在必要时交换它们，然后我重复这个直到我发现他上面的玩家的分数大于他的分数或直到他到达列表的顶部。问题在于它的最坏情况时间为 O (n)，是否可以在 O (log n) 之类的情况下完成？？

Answer 1

维护 balanced search tree ，映射玩家得分。当玩家n的分数变化z时，

1. 找到n的当前值，说y

2. 删除n

   的条目

3. 插入一个从n到y + z

   的映射

复杂度是对数的。