难度: Medium
Submission
运行时间: 42 ms
内存: 16.9 MB
from sortedcontainers import SortedDict
class Leaderboard:
def __init__(self):
self.scores = {}
self.sortedScores = SortedDict()
def addScore(self, playerId: int, score: int) -> None:
# 分数字典只包含从 playerID 到它们的分数的映射。
# sortedScores 包含一个 BST，
# 其中 key 作为比分，value 作为拥有该比分的球员的数量。
if playerId not in self.scores:
self.scores[playerId] = score
self.sortedScores[-score] = self.sortedScores.get(-score, 0) + 1
else:
preScore = self.scores[playerId]
val = self.sortedScores.get(-preScore) # 只有一个
if val == 1:
del self.sortedScores[-preScore]
else:
self.sortedScores[-preScore] = val - 1
newScore = preScore + score
self.scores[playerId] = newScore
self.sortedScores[-newScore] = self.sortedScores.get(-newScore, 0) + 1
def top(self, K: int) -> int:
count, total = 0, 0
for key, value in self.sortedScores.items():
times = self.sortedScores.get(key)
for _ in range(times):
total += -key
count += 1
# 找到 top-K分数，break。
if count == K:
break
# 找到 top-K分数，break。
if count == K:
break
return total
def reset(self, playerId: int) -> None:
preScore = self.scores[playerId]
if self.sortedScores[-preScore] == 1:
del self.sortedScores[-preScore]
else:
self.sortedScores[-preScore] -= 1
del self.scores[playerId]
# class Leaderboard:
# def __init__(self):
# self.dic = set([])
# self.deq = []
# def addScore(self, playerId: int, score: int) -> None:
# if playerId not in self.dic:
# self.dic.add(playerId)
# if not self.deq:
# self.deq.insert(0, (score, playerId))
# if self.deq[-1][0] > score:
# self.deq.append((score, playerId))
# for idx, i in enumerate(self.deq):
# if i[0] < score:
# self.deq.insert(idx, (score, playerId))
# break
# else:
# for idx, i in enumerate(self.deq):
# if i[1] == playerId:
# score += i[0]
# tmp = idx
# while tmp > 0 and score > self.deq[tmp][0]:
# self.deq[tmp] = self.deq[tmp - 1]
# tmp -= 1
# self.deq[tmp] = (score, playerId)
# break
# def top(self, K: int) -> int:
# return sum([self.deq[i][0] for i in range(min(K, len(self.deq)))])
# def reset(self, playerId: int) -> None:
# self.dic.remove(playerId)
# for idx, i in enumerate(self.deq):
# if i[1] == playerId:
# self.deq.pop(idx)
# break
# Your Leaderboard object will be instantiated and called as such:
# obj = Leaderboard()
# obj.addScore(playerId,score)
# param_2 = obj.top(K)
# obj.reset(playerId)
Explain
这个题解利用了Python的SortedDict来维护一个有序的字典，其中键表示分数（以负数形式存储以保持最大的分数在前），值表示该分数对应的玩家数量。这允许快速增加分数、重置分数和计算前K高分的总和。具体操作如下： 1. 在增加分数时，首先检查玩家是否已存在。如果不存在，直接添加；如果存在，更新分数，并调整SortedDict中的统计。 2. 计算前K高分的总和时，从SortedDict开始累加最高的分数，直到达到K个。 3. 重置玩家分数时，将该玩家的分数从SortedDict中减去，并从scores字典中删除玩家。
时间复杂度: O(log n) for addScore and reset, O(K) for top
空间复杂度: O(p)
from sortedcontainers import SortedDict
class Leaderboard:
def __init__(self):
self.scores = {} # 玩家ID映射到分数
self.sortedScores = SortedDict() # 存储分数和相应的玩家数量
def addScore(self, playerId: int, score: int) -> None:
if playerId not in self.scores:
self.scores[playerId] = score
self.sortedScores[-score] = self.sortedScores.get(-score, 0) + 1
else:
preScore = self.scores[playerId]
if self.sortedScores[-preScore] == 1:
del self.sortedScores[-preScore]
else:
self.sortedScores[-preScore] -= 1
newScore = preScore + score
self.scores[playerId] = newScore
self.sortedScores[-newScore] = self.sortedScores.get(-newScore, 0) + 1
def top(self, K: int) -> int:
count, total = 0, 0
for key, value in self.sortedScores.items():
times = value
for _ in range(times):
total += -key
count += 1
if count == K:
break
if count == K:
break
return total
def reset(self, playerId: int) -> None:
preScore = self.scores[playerId]
if self.sortedScores[-preScore] == 1:
del self.sortedScores[-preScore]
else:
self.sortedScores[-preScore] -= 1
del self.scores[playerId]
Explore
当一个特定的分数值从`SortedDict`中完全删除（即没有任何玩家拥有该分数时），然后该分数值再次出现时，它将被作为一个新的键重新插入到`SortedDict`中。这是因为`SortedDict`维护键的有序特性，每个键对应一个或多个玩家的相同分数。当新的或已存在的玩家获得这个分数时，`SortedDict`会检查这个分数（作为键）是否存在，如果不存在，就新增这个键，并设置其对应的玩家数量；如果已存在，则更新该键对应的玩家数量。
选择使用`SortedDict`的主要原因是其能够维持键的有序性。这使得在执行诸如计算前K高分总和这类操作时更为高效，因为可以直接从最高分开始累加，直到达到所需的K值。如果使用普通字典，每次需要计算最高分时都必须对分数进行排序，这会增加额外的计算成本。而优先队列虽然可以维持元素的有序性，但它不便于对特定分数的查找和修改，如增加或减少特定分数的玩家数量，这对于本问题是必需的。因此，`SortedDict`在此类应用中提供了既高效又方便的解决方案。
在`top`方法中，时间复杂度主要依赖于K的大小以及SortedDict中的元素数量。在最坏情况下，如果K很大，可能需要遍历整个SortedDict，其时间复杂度为O(K)。尽管这种方法已经相对高效（因为SortedDict已经按照分数排序），但如果频繁查询前K高分，可以考虑使用更高效的数据结构，如平衡二叉搜索树（例如红黑树），在其中维护一个累加的分数总和，这样可以进一步优化到O(log N)的时间复杂度进行查询。然而，这将需要更复杂的实现和额外的空间来维护节点的累积值。