golang 解法, 执行用时: 12 ms, 内存消耗: 6.3 MB, 提交时间: 2023-10-22 08:31:36

type Leaderboard struct {
    item []Item
    exists map[int]bool
}

type Item struct {
    score int
    id int
}

func Constructor() Leaderboard {
    return Leaderboard{
        item: []Item{},
        exists: map[int]bool{},
    }
}


func (this *Leaderboard) AddScore(playerId int, score int)  {
    if _, ok := this.exists[playerId]; !ok {
        this.exists[playerId] = true
        this.item = append(this.item, Item{score, playerId})
    } else {
        for i := 0; i < len(this.item); i++ {
            if this.item[i].id == playerId {
                this.item[i].score += score
                break
            }
        }
    }
}


func (this *Leaderboard) Top(K int) int {
    sort.Slice(this.item, func(i, j int) bool {
        return this.item[i].score > this.item[j].score
    })
    score := 0
    for i := 0; i < K; i++ {
        score += this.item[i].score
    }
    return score
}


func (this *Leaderboard) Reset(playerId int)  {
    for i := 0; i < len(this.item); i++ {
        if this.item[i].id == playerId {
            this.item[i].score = 0
            break
        }
    }
}

/**
 * Your Leaderboard object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddScore(playerId,score);
 * param_2 := obj.Top(K);
 * obj.Reset(playerId);
 */

golang 解法, 执行用时: 8 ms, 内存消耗: 6.4 MB, 提交时间: 2023-10-22 08:30:42

type Leaderboard struct {
	board map[int]int
}

func Constructor() Leaderboard {
	return Leaderboard{board:map[int]int{}}
}

func (l *Leaderboard) AddScore(playerId int, score int) {
	l.board[playerId] += score
}

func (l *Leaderboard) Top(K int) int {
	var a = make([]int, len(l.board))
	index := 0
	for _, i := range l.board {
		a[index] = i
        index++
	}
	topK(a, K)
	ans := 0
	for i := len(a) - K; i < len(a); i++ {
		ans += a[i]
	}
	return ans
}

func (l *Leaderboard) Reset(playerId int) {
	l.board[playerId] = 0
}
// 快速选择topk
func topK(a []int, k int) {
	l, h := 0, len(a)-1
	temp := a[l]
	for l < h {
		for h > l && a[h] >= temp {
			h--
		}
		a[h], a[l] = a[l], a[h]
		for l < h && a[l] < temp {
			l++
		}

		a[h], a[l] = a[l], a[h]
	}
	if l+k == len(a) {
		return
	}
	if l+k < len(a) {
		topK(a[l+1:], k)
		return
	}
	topK(a[:l], k+l-len(a))
}

/**
 * Your Leaderboard object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddScore(playerId,score);
 * param_2 := obj.Top(K);
 * obj.Reset(playerId);
 */

cpp 解法, 执行用时: 12 ms, 内存消耗: 11.2 MB, 提交时间: 2023-10-22 08:30:03

class Leaderboard {
public:
    unordered_map<int, int> id_score;
    multiset<int> m;

    Leaderboard() {
    }
    
    void addScore(int playerId, int score) {
        if (id_score.find(playerId) == id_score.end())
        {
            id_score[playerId] = score;
            m.insert(score);
        }
        else
        {
            int old_score = id_score[playerId];
            id_score[playerId] += score;
            m.erase(m.find(old_score));
            m.insert(id_score[playerId]);
        }
    }
    
    int top(int K) {
        int res = 0;
        int cnt = 0;
        for (auto it = m.rbegin(); it != m.rend(); it ++) {
            if (cnt == K)
                break;
            res += (*it);
            cnt ++;
        }
        return res;
    }
    
    void reset(int playerId) {
        int old_score = id_score[playerId];
        id_score.erase(playerId);
        m.erase(m.find(old_score));
    }
};

/**
 * 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);
 */

python3 解法, 执行用时: 60 ms, 内存消耗: 16.8 MB, 提交时间: 2023-10-22 08:29:20

from sortedcontainers import SortedList as SL

class Leaderboard:

    def __init__(self):
        self.maxSL = SL()       #最大，可重复，有序，集合
        self.id_score = defaultdict()   #参赛者id--分数

    def addScore(self, playerId: int, score: int) -> None:
        if playerId not in self.id_score:
            self.id_score[playerId] = score
            self.maxSL.add(- score)             # *（-1），排序方式改变
        else:
            old_val = self.id_score[playerId]
            self.id_score[playerId] += score
            self.maxSL.remove(- old_val)
            self.maxSL.add(- self.id_score[playerId])

    def top(self, K: int) -> int:
        res = 0
        cnt = 0
        for score in self.maxSL:
            if cnt == K:
                break
            score *= (-1)
            res += score
            cnt += 1
        return res

    def reset(self, playerId: int) -> None:
        score = self.id_score[playerId]
        self.id_score.pop(playerId)
        self.maxSL.remove(-score)

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

java 解法, 执行用时: 8 ms, 内存消耗: 42.5 MB, 提交时间: 2023-10-22 08:28:14

/*
【平衡树】
*/
class Leaderboard {
    TreeMap<Integer, Set<Integer>> map;
    Map<Integer, Integer> playerScore;

    public Leaderboard() {
        map = new TreeMap<>((a, b) -> b - a);
        playerScore = new HashMap<>();
    }

    public void addScore(int playerId, int score) {
        int lastScore = playerScore.getOrDefault(playerId, 0);
        playerScore.put(playerId, lastScore + score);
        if (lastScore > 0) {
            map.get(lastScore).remove(playerId);
        }
        if (!map.containsKey(lastScore + score)) map.put(lastScore +  score, new HashSet<>());
        map.get(lastScore + score).add(playerId);
    }

    public int top(int K) {
        int res = 0;
        for (int score : map.keySet()) {
            res += score * Math.min(K, map.get(score).size());
            K -= map.get(score).size();
            if (K <= 0) return res;
        }
        return res;
    }

    public void reset(int playerId) {
        map.get(playerScore.remove(playerId)).remove(playerId);
    }
}

/**
 * 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);
 */