1244. Design A Leaderboard

https://leetcode.com/problems/design-a-leaderboard/leetcode.com

addScore 和reset 都很好解决，主要是处理top(K) 的问题，找一个无序 array 排序后的前 K 个元素：

1. 可以用quick select 来固定第K个元素的位置，然后它前面的就都是比它小/大的。

2. 维护一个长度K的最大堆max heap。

原题要会员，最后附一下题目。

max heap

class Leaderboard:

    def __init__(self):
        self.scores = defaultdict(int)
        
    # O(1)
    def addScore(self, playerId: int, score: int) -> None:
        self.scores[playerId] += score
        
    # O(logN+log(N-K)).
    def top(self, K: int) -> int:
        heap = []
        for score in self.scores.values():
            if len(heap) < K:
                heapq.heappush(heap, score)
            else:
                heapq.heappushpop(heap, score)
        return sum(heap)
    
    # O(1)
    def reset(self, playerId: int) -> None:
        if playerId in self.scores:
            self.scores.pop(playerId)


# Your Leaderboard object will be instantiated and called as such:
# obj = Leaderboard()
# obj.addScore(playerId,score)
# param_2 = obj.top(K)
# obj.reset(playerId)

quick select

class Leaderboard:
    def __init__(self):
        self.scores = defaultdict(int)
        
    # O(1)
    def addScore(self, playerId: int, score: int) -> None:
        self.scores[playerId] += score
        
    # Average time complexity should be O(N). Worst-case is O(N^2).
    def top(self, K: int) -> int:
        unsorted = list(self.scores.values()) # Have to make this a list, otherwise Python throws an exception saying we can index dict_values.
        self.quickSelect(unsorted, K - 1, 0, len(unsorted) - 1)
        
        return sum(unsorted[:K])
    
    # Use QuickSelect but sort in reverse order. 
    # We did just for no reason other than it simplifies the code in the return statement of top().
    def quickSelect(self, arr, K, p, q):
        partitionIndex = self.partition(arr, p, q)
        if partitionIndex == K:
            return None
        elif partitionIndex > K:
            # Going left.
            self.quickSelect(arr, K, p, partitionIndex - 1)
        else:
            # Going right.
            self.quickSelect(arr, K, partitionIndex + 1, q)
    
    def partition(self, arr, l, r):
        pivot = arr[r] # choose the last element as the pivot
        i = l
        for j in range(l, r):
            if arr[j] >= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[r] = arr[r], arr[i]
        return i
    
    # O(1)
    def reset(self, playerId: int) -> None:
        if playerId in self.scores:
            del self.scores[playerId]

原题

Design a Leaderboard class, which has 3 functions:

1. addScore(playerId, score): Update the leaderboard by adding score to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score.

2. top(K): Return the score sum of the top K players.

3. reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.

Initially, the leaderboard is empty.

Example 1:

Input: 
["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]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

Explanation: 
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;