Leetcode 1244:力扣排行榜(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1244:力扣排行榜(超详细的解法!!!)

in leetcode with 0 comment

新一轮的「力扣杯」编程大赛即将启动,为了动态显示参赛者的得分数据,需要设计一个排行榜 Leaderboard。

请你帮忙来设计这个 Leaderboard 类,使得它有如下 3 个函数:

  1. addScore(playerId, score)

    • 假如参赛者已经在排行榜上,就给他的当前得分增加 score 点分值并更新排行。
    • 假如该参赛者不在排行榜上,就把他添加到榜单上,并且将分数设置为 score
  2. top(K):返回前 K 名参赛者的 得分总和
  3. reset(playerId):将指定参赛者的成绩清零。题目保证在调用此函数前,该参赛者已有成绩,并且在榜单上。

请注意,在初始状态下,排行榜是空的。

示例 1:

输入: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
输出:
[null,null,null,null,null,null,73,null,null,null,141]

解释: 
Leaderboard leaderboard = new Leaderboard ();
leaderboard.addScore(1,73);   // leaderboard = [[1,73]];
leaderboard.addScore(2,56);   // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39);   // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51);   // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4);    // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1);           // returns 73;
leaderboard.reset(1);         // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
leaderboard.reset(2);         // leaderboard = [[3,39],[4,51],[5,4]];
leaderboard.addScore(2,51);   // leaderboard = [[2,51],[3,39],[4,51],[5,4]];
leaderboard.top(3);           // returns 141 = 51 + 51 + 39;

提示:

解题思路

设计题,我们可以通过字典去存储[playerId, score],计算topK的时候,可以将socre排序。

class Leaderboard:
    def __init__(self):
        self.d = collections.defaultdict(int)

    def addScore(self, playerId: int, score: int) -> None:
        self.d[playerId] += score

    def top(self, K: int) -> int:
        return sum(sorted([v for k, v in self.d.items()], reverse=True)[:K])

    def reset(self, playerId: int) -> None:
        del self.d[playerId]

addScorereset的时间复杂度都是O(1)topK的时间复杂度是O(nlogn)。我们可以通过堆来优化topK的时间复杂度

return sum(heapq.nlargest(K, self.d.values()))

此时topK的时间复杂度是O(nlogK)

使用collections.Counter内置的most_common函数也可以实现。

class Leaderboard:
    def __init__(self):
        self.d = collections.Counter()

    def addScore(self, playerId: int, score: int) -> None:
        self.d[playerId] += score

    def top(self, K: int) -> int:
        return sum(v for _, v in self.d.most_common(K))

    def reset(self, playerId: int) -> None:
        del self.d[playerId]

cpp中可以使用map来做,addScorereset的时间复杂度就是O(logn)topK的时间复杂度就是O(K)

reference:

https://leetcode.com/problems/design-a-leaderboard/discuss/418866/Python-Counter-1-line-Each

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses