题目描述
请你帮忙来设计这个 Leaderboard
类,使得它有如下 3 个函数:
addScore(playerId, score)
:- 假如参赛者已经在排行榜上,就给他的当前得分增加
score
点分值并更新排行。 - 假如该参赛者不在排行榜上,就把他添加到榜单上,并且将分数设置为
score
。
- 假如参赛者已经在排行榜上,就给他的当前得分增加
top(K)
:返回前K
名参赛者的得分总和。reset(playerId)
:将指定参赛者的成绩清零。题目保证在调用此函数前,该参赛者已有成绩,并且在榜单上。
初始状态下,排行榜是空的。
样例
输入:
["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
次函数调用。
算法
(暴力模拟) 更新 $O(n)$,查询 $O(n \log K)$
- 添加分数时,扫一遍数组,如果存在
playerId
,则直接更新分数。否则添加一个新的分数。 reset
时,扫一遍数组,然后把分数置0
。- 查询时,扫一遍数组,同时维护一个容量为
K
小根堆,如果当前分数大于小根堆的堆顶,则堆顶出堆,当前分数入堆。
时间复杂度
- 更新时需要扫数组,故时间复杂度为 $O(n)$。
- 查询时,扫数组的同时可能需要维护堆,故时间复杂度为 $O(n \log K)$。
空间复杂度
- 需要一个数组维护所有成员的分数,查询时需要长度为 $K$ 的优先队列。
- 故总的空间复杂度为 $O(n)$。
C++ 代码
class Leaderboard {
public:
vector<pair<int, int>> player;
Leaderboard() {
}
void addScore(int playerId, int score) {
for (int i = 0; i < player.size(); i++)
if (player[i].first == playerId) {
player[i].second += score;
return;
}
player.emplace_back(playerId, score);
}
int top(int K) {
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < player.size(); i++) {
if (q.size() < K)
q.push(player[i].second);
else {
if (player[i].second > q.top()) {
q.pop();
q.push(player[i].second);
}
}
}
int ans = 0;
while (!q.empty()) {
ans += q.top();
q.pop();
}
return ans;
}
void reset(int playerId) {
for (int i = 0; i < player.size(); i++)
if (player[i].first == playerId) {
player[i].second = 0;
}
}
};
/**
* Your Leaderboard object will be instantiated and called as such:
* Leaderboard* obj = new Leaderboard();
* obj->addScore(playerId,score);
* int param_2 = obj->top(K);
* obj->reset(playerId);
*/