# 1244. Design A Leaderboard
###### tags: `Leetcode` `Medium` `Bloomberg`
Link: https://leetcode.com/problems/design-a-leaderboard/
## 思路
### 思路一
用HashMap和Priority Queue
**注意写法: 这里的priority queue里面的每个element都是Map.Entry**
### 思路二
用TreeMap存score和对应的人数，TreeMap可以对key排序
**注意写法: TreeMap 本来是increasing order的，但是通过```new TreeMap<>(Collections.reverseOrder());```可以让他变成decreasing order**
## Code
### 思路一 O(1) O(1) O(NlogK)

class Leaderboard:

    def __init__(self):
        self.scores = collections.defaultdict(int)
        self.pq = []

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

    def top(self, K: int) -> int:
        for score in self.scores.values():
          heapq.heappush(self.pq, score)
          if len(self.pq)>K:
            heapq.heappop(self.pq)
        total = 0
        for score in self.pq:
          total += score
        self.pq = []
        return total

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

class Leaderboard {
    Map<Integer,Integer> scores;
    public Leaderboard() {
        scores = new HashMap<>();
    }
    
    public void addScore(int playerId, int score) {
        scores.put(playerId, scores.getOrDefault(playerId, 0)+score);
    }
    
    public int top(int K) {
        Queue<Map.Entry<Integer,Integer>> q = new PriorityQueue<>((a,b)->(a.getValue()-b.getValue()));
        
        for(Map.Entry<Integer, Integer> entry: scores.entrySet()){
            q.offer(entry);
            if(q.size()>K){
                q.poll();
            }
        }
        
        int total = 0;
        for(Map.Entry<Integer,Integer> entry:q){
            total+=entry.getValue();
        }
        return total;
    }
    
    public void reset(int playerId) {
        scores.remove(playerId);
    }
}

### 思路二 O(logN) O(logN) O(K)

class Leaderboard {
    Map<Integer,Integer> scores;
    Map<Integer,Integer> sortedScores;
    public Leaderboard() {
        scores = new HashMap<>();
        sortedScores = new TreeMap<>(Collections.reverseOrder());
    }
    
    public void addScore(int playerId, int score) {
        if(!scores.containsKey(playerId)){
            scores.put(playerId, score);
            sortedScores.put(score, sortedScores.getOrDefault(score, 0)+1);
        }
        else{
            int preScore = scores.get(playerId);
            int preScoreCnt = sortedScores.get(preScore);
            if(preScoreCnt == 1) sortedScores.remove(preScore);
            else{
                sortedScores.put(preScore, preScoreCnt-1);
            }
            sortedScores.put(preScore+score, sortedScores.getOrDefault(preScore+score, 0)+1);
            scores.put(playerId, preScore+score);
        }
    }
    
    public int top(int K) {
        int total = 0;
        int count = 0;
        for(Map.Entry<Integer, Integer> entry: sortedScores.entrySet()){
            int times = entry.getValue();
            int score = entry.getKey();
            
            if(count+times < K){
                count += times;
                total += times*score;
            }
            else{
                total += (K-count)*score;
                count = K;
                break;
            }
        }
        return total;
    }
    
    public void reset(int playerId) {
        int preScore = scores.get(playerId);
        int preScoreCnt = sortedScores.get(preScore);
        if(preScoreCnt == 1) sortedScores.remove(preScore);
        else{
            sortedScores.put(preScore, preScoreCnt-1);
        }
        
        scores.remove(playerId);
    }
}