leetcode
leetcode 1001 ~ 1050
力扣排行榜

力扣排行榜

难度:

标签:

题目描述

代码结果

运行时间: 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`中完全删除(即没有任何玩家拥有该分数时),然后该分数值再次出现时,它将被作为一个新的键重新插入到`SortedDict`中。这是因为`SortedDict`维护键的有序特性,每个键对应一个或多个玩家的相同分数。当新的或已存在的玩家获得这个分数时,`SortedDict`会检查这个分数(作为键)是否存在,如果不存在,就新增这个键,并设置其对应的玩家数量;如果已存在,则更新该键对应的玩家数量。
🦆
为什么选择使用SortedDict来维护分数和玩家数量,而不是选择其他数据结构,比如普通的字典或者优先队列?
选择使用`SortedDict`的主要原因是其能够维持键的有序性。这使得在执行诸如计算前K高分总和这类操作时更为高效,因为可以直接从最高分开始累加,直到达到所需的K值。如果使用普通字典,每次需要计算最高分时都必须对分数进行排序,这会增加额外的计算成本。而优先队列虽然可以维持元素的有序性,但它不便于对特定分数的查找和修改,如增加或减少特定分数的玩家数量,这对于本问题是必需的。因此,`SortedDict`在此类应用中提供了既高效又方便的解决方案。
🦆
在`top`方法中,通过逐个遍历SortedDict的元素来计算前K高分的总和,这种方法的时间复杂度是多少?是否存在更高效的方式?
在`top`方法中,时间复杂度主要依赖于K的大小以及SortedDict中的元素数量。在最坏情况下,如果K很大,可能需要遍历整个SortedDict,其时间复杂度为O(K)。尽管这种方法已经相对高效(因为SortedDict已经按照分数排序),但如果频繁查询前K高分,可以考虑使用更高效的数据结构,如平衡二叉搜索树(例如红黑树),在其中维护一个累加的分数总和,这样可以进一步优化到O(log N)的时间复杂度进行查询。然而,这将需要更复杂的实现和额外的空间来维护节点的累积值。

相关问题