我想维护一个记分板,其中包含N名球员,根据他们的分数排序,我所做的是:
当我得到x分时(如果他还不是头号球员),我将他的得分与他上面球员的得分进行比较,必要时进行交换,然后重复此操作,直到我发现他上面的球员得分大于他的得分,或者直到他达到列表的顶部。
问题是它的最坏情况时间是o(n),它可以在o(logn)这样的东西中完成吗?是吗?
最佳答案
保持abalanced search tree,将玩家映射到得分当玩家n的分数变为z时,
求n的当前值,比如y
删除n的条目
插入从n到y+z的映射
复杂性是对数的。