力扣排行榜
难度:
标签:
题目描述
代码结果
运行时间: 42 ms, 内存: 16.9 MB
import java.util.HashMap;
import java.util.Map;
public class Leaderboard {
private Map<Integer, Integer> scores;
/**
* Constructor to initialize the leaderboard.
*/
public Leaderboard() {
scores = new HashMap<>();
}
/**
* Add score for the player. If the player does not exist, add the player with initial score.
* @param playerId Player's unique ID.
* @param score The score to add.
*/
public void addScore(int playerId, int score) {
scores.put(playerId, scores.getOrDefault(playerId, 0) + score);
}
/**
* Return the sum of the top K scores using Java Streams.
* @param K Number of top scores to sum.
* @return Sum of the top K scores.
*/
public int top(int K) {
return scores.values().stream()
.sorted((a, b) -> b - a)
.limit(K)
.mapToInt(Integer::intValue)
.sum();
}
/**
* Reset the score of the player to zero.
* @param playerId Player's unique ID.
*/
public void reset(int playerId) {
scores.remove(playerId);
}
}
解释
方法:
这个题解利用了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)
代码细节讲解
🦆
在`addScore`方法中,如果一个玩家的分数从SortedDict中删除,那么当该分数值再次出现时,SortedDict是如何处理的?
▷🦆
为什么选择使用SortedDict来维护分数和玩家数量,而不是选择其他数据结构,比如普通的字典或者优先队列?
▷🦆
在`top`方法中,通过逐个遍历SortedDict的元素来计算前K高分的总和,这种方法的时间复杂度是多少?是否存在更高效的方式?
▷