LEETCODE 1244. Design A Leaderboard 解题思路分析

题目大意：

设计排行榜

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

addScore(playerId, score)：
假如参赛者已经在排行榜上，就给他的当前得分增加 score 点分值并更新排行。
假如该参赛者不在排行榜上，就把他添加到榜单上，并且将分数设置为 score。

top(K)：返回前 K 名参赛者的得分总和。

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;

提示：

• 1 <= playerId, K <= 10000
• 题目保证 K 小于或等于当前参赛者的数量。
• 1 <= score <= 100
• 最多进行 1000 次函数调用。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1244

解题思路分析：

本题要考虑到两点：

1. 如何存储数据
2. 如何排序数据

考虑到参赛者与得分是一一对应关系，因此使用key-value的存储方式比较合理。在查找排名靠前的参赛者时，我们应先对数据以value的值做降序排列，然后再取出前K位即可。

实现代码：

// 利用map存储数据，key为参赛者id，value为积分
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public Leaderboard() {

}

public void addScore(int playerId, int score) {
    // 取得该参赛者之前的积分，默认为0
    int s = map.getOrDefault(playerId, 0);
    // 加上当前积分后再保存进map
    map.put(playerId, s + score);
}

public int top(int K) {
    // 将map进行倒序排序排序
    List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
    list.sort(Collections.reverseOrder(Map.Entry.comparingByValue()));
    // 取得前K位的和
    int sum=0;
    for(int i=0;i<K;i++){
        Map.Entry<Integer, Integer> entry = list.get(i);
        sum+=entry.getValue();
    }
    return sum;
}

public void reset(int playerId) {
    map.put(playerId, 0);
}

本解法运行时间为32ms。

Runtime: 32 ms, faster than 72.08% of Java online submissions for Design A Leaderboard.

Memory Usage: 38.3 MB, less than 100.00% of Java online submissions for Design A Leaderboard.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1244-design-a-leaderboard-解题思路分析/