设计排行榜哈希表、最小堆与 TreeMap 三种数据结构方案详解LeetCode 1393【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇基于本仓库的算法解析文档 design-a-leaderboard.md 展开系统讲解如何设计一个支持addScore、top(K)、reset三个操作的在线排行榜数据结构。读完你将掌握为什么朴素「哈希表 全量排序」在top查询上的开销是 O(N log N)、如何用大小为 K 的最小堆将其降到 O(N log K)、以及「玩家分数映射 分数计数的有序映射」双结构如何把top优化到 O(K)并理解各方案中分数变更时的计数回滚细节与三大典型陷阱。问题定义题目要求实现Leaderboard类提供三个 API语义可从文档中的各语言实现直接确认addScore(playerId, score)给指定玩家累加分数。若玩家不存在则初始化若存在则在其原有分数基础上累加top(K)返回当前前 K 名玩家分数之和reset(playerId)清空该玩家的分数。设计目标是在大量玩家、频繁调用top的场景下让每个操作尽可能高效。下面按「暴力 → 堆优化 → 有序映射」的递进顺序展开三种方案全部代码以文档中的 Python 与 Java 为主版本并总结 C、Go、Rust、Kotlin、Swift、C#、JavaScript 八种语言实现的差异点。前置知识文档在开头明确列出了本题需要的四项基础能力哈希表Hash Maps以 O(1) 存取与更新玩家分数堆 / 优先队列Heaps / Priority Queues不排序全体即可高效找出 Top-K 元素有序映射 / TreeMapSorted Maps / TreeMaps维护分数的有序状态以支持高效的范围查询排序Sorting理解降序排序这是暴力方案的基石。方案一哈希表 全量排序暴力直觉最简单的做法是用哈希表scores存储playerId → score映射。加分与重置都是 O(1) 的哈希操作top(K)则取出全部分数、降序排序、累加前 K 个。实现简单但当玩家很多且top查询频繁时每次都要对 N 个分数做 O(N log N) 排序效率低下。算法步骤用哈希表scores维护playerId → score映射addScore(playerId, score)玩家存在则累加不存在则初始化后再累加top(K)提取所有分数值降序排序返回前 K 个分数之和reset(playerId)把该玩家分数置为0。参考实现Python 版本文档原文此处使用defaultdict()等价写法推荐显式指定默认类型为defaultdict(int)from collections import defaultdict class Leaderboard: def __init__(self): self.scores defaultdict(int) def addScore(self, playerId: int, score: int) - None: self.scores[playerId] score def top(self, K: int) - int: values list(self.scores.values()) values.sort(reverseTrue) total, i 0, 0 while i K: total values[i] i 1 return total def reset(self, playerId: int) - None: self.scores[playerId] 0Java 版本保留文档中关于容器选择的说明class Leaderboard { private HashMapInteger, Integer scores; public Leaderboard() { // 单线程场景下无需同步访问HashMap 相比 Hashtable 是更合适的选择 this.scores new HashMapInteger, Integer(); } public void addScore(int playerId, int score) { if (!this.scores.containsKey(playerId)) { this.scores.put(playerId, 0); } this.scores.put(playerId, this.scores.get(playerId) score); } public int top(int K) { ListInteger values new ArrayListInteger(this.scores.values()); Collections.sort(values, Collections.reverseOrder()); int total 0; for (int i 0; i K; i) { total values.get(i); } return total; } public void reset(int playerId) { this.scores.put(playerId, 0); } }其他语言的关键实现细节文档同时给出了 C、JavaScript、C#、Go、Kotlin、Swift、Rust 共七种语言的等价实现核心差异值得注意Cunordered_map加分时直接scores[playerId] scoreoperator[]自动初始化为 0排序用sort(values.begin(), values.end(), greaterint())降序Go结构体方法直接this.scores[playerId] score排序用sort.Sort(sort.Reverse(sort.IntSlice(values)))Kotlin利用scores.getOrDefault(playerId, 0) score一行完成累加scores.values.sortedDescending()一步降序Swift字典下标默认值语法scores[playerId, default: 0] score是最简洁的写法scores.values.sorted(by: )降序Rust*self.scores.entry(player_id).or_insert(0) score是 entry API 的经典用法values.iter().take(k as usize).sum()一行求和C# / JavaScript分别用Dictionaryint,int/Map排序后取前 K 个求和逻辑与 Java 一致。复杂度设 N 为排行榜总玩家数时间addScoreO(1)resetO(1)topO(N log N)空间O(N)。方案二大小为 K 的最小堆求 Top-K直觉不必对全部 N 个分数排序。用一个大小为 K 的最小堆扫描所有分数每压入一个分数后若堆大小超过 K就弹出堆顶当前 K1 个中最大的那个里的最小者。处理完全部分数后堆里恰好剩下的就是最大的 K 个分数直接求和即可。算法步骤哈希表scores同方案一addScore同方案一top(K)建一个最小堆逐个压入每个分数堆大小超过 K 时弹出最小元素全部处理完后累加堆中剩余元素reset同方案一。参考实现Python 版本利用heapq默认即最小堆的特性import heapq class Leaderboard: def __init__(self): self.scores {} def addScore(self, playerId: int, score: int) - None: if playerId not in self.scores: self.scores[playerId] 0 self.scores[playerId] score def top(self, K: int) - int: # Python 默认是最小堆 heap [] for x in self.scores.values(): heapq.heappush(heap, x) if len(heap) K: heapq.heappop(heap) res 0 while heap: res heapq.heappop(heap) return res def reset(self, playerId: int) - None: self.scores[playerId] 0Java 版本需自定义比较器构造最小堆文档注释特别强调了这一点class Leaderboard { private HashMapInteger, Integer scores; public Leaderboard() { this.scores new HashMapInteger, Integer(); } public void addScore(int playerId, int score) { if (!this.scores.containsKey(playerId)) { this.scores.put(playerId, 0); } this.scores.put(playerId, this.scores.get(playerId) score); } public int top(int K) { // Java 中的最小堆存放哈希表的 entry。 // 必须提供自定义比较器才能保证按分数比较得到正确顺序。 PriorityQueueMap.EntryInteger, Integer heap new PriorityQueue((a, b) - a.getValue() - b.getValue()); for (Map.EntryInteger, Integer entry : this.scores.entrySet()) { heap.offer(entry); if (heap.size() K) { heap.poll(); } } int total 0; Iterator value heap.iterator(); while (value.hasNext()) { total ((Map.EntryInteger, Integer)value.next()).getValue(); } return total; } public void reset(int playerId) { this.scores.put(playerId, 0); } }各语言的最小堆构造差异这是文档中信息量最大的部分不同标准库的默认堆方向不同是实战中最容易写错的地方Cpriority_queue默认是最大堆因此需要写priority_queueint, vectorint, greaterint翻转为最小堆Go标准库container/heap不内置数值堆文档实现自定义了MinHeap []int类型实现Len、Lessh[i] h[j]保证最小堆语义、Swap、Push、Pop五个接口配合heap.Init/heap.Push/heap.Pop使用RustBinaryHeap默认最大堆文档用heap.push(Reverse(score))包装std::cmp::Reverse实现最小堆语义最后heap.into_iter().map(|Reverse(v)| v).sum()求和KotlinPriorityQueueInt()天然按自然序即最小堆C#.NET 的PriorityQueueint,int本身是最小堆直接Enqueue(score, score)即可JavaScript原生无堆文档借助datastructures-js/priority-queue包并以比较器(a, b) a - b构造最小堆Swift标准库同样没有堆文档用数组模拟每插入一个分数就heap.sort()后removeFirst()删最小值——逻辑正确但每次插入都排序实际上退化为 O(N·K log K) 的模拟写法属于演示性实现。复杂度时间addScoreO(1)resetO(1)topO(N log K)每次 push/pop 摊还 O(log K)共 N 次空间O(N K)其中 K 为堆的容量。当 K 远小于 N 时log K 显著小于 log N这是相对暴力方案的核心收益。方案三TreeMap / SortedMap 分数计数直觉有序映射JavaTreeMap、PythonSortedDict等天然维护键的有序性。关键洞察是用「分数 → 拥有该分数的玩家人数」的计数映射而不是逐玩家存储。分数变化时对旧分数计数减一归零则删键、对新分数计数加一top(K)只需从高分到低分迭代按人数累加直到凑满 K 个玩家即可完全不需要遍历全部玩家。双结构设计scores哈希表playerId → 当前分数O(1) 定位玩家sortedScores有序映射分数 → 该分数的玩家人数按降序排列Java 用new TreeMap(Collections.reverseOrder())Python 因SortedDict只能升序用负数-score作键来模拟降序C# 用自定义ComparerRust 用BTreeMapReversei32, i32Go 则手写降序数组。算法步骤双结构初始化同上addScore(playerId, score)玩家为新玩家分数与计数直接写入两个结构玩家已存在把旧分数在sortedScores中的计数减一计数为 1 时删除该键更新scores中的新分数再把新分数计数加一top(K)降序遍历sortedScores对每个分数按人数逐次累加直到累计玩家数达到 Kreset(playerId)把该玩家分数在sortedScores中计数减一归零删键并从scores中删除玩家。参考实现Python 版本文档原文的完整逻辑-score反转技巧是精华所在from sortedcontainers import SortedDict class Leaderboard: def __init__(self): self.scores {} self.sortedScores SortedDict() def addScore(self, playerId: int, score: int) - None: # scores 存储 playerId - 分数sortedScores 以分数为键取负模拟降序 # 值为拥有该分数的玩家人数。 if playerId not in self.scores: self.scores[playerId] score self.sortedScores[-score] self.sortedScores.get(-score, 0) 1 else: preScore self.scores[playerId] val self.sortedScores.get(-preScore) if val 1: del self.sortedScores[-preScore] else: self.sortedScores[-preScore] val - 1 newScore preScore score self.scores[playerId] newScore self.sortedScores[-newScore] self.sortedScores.get(-newScore, 0) 1 def top(self, K: int) - int: count, total 0, 0 for key, value in self.sortedScores.items(): times self.sortedScores.get(key) for _ in range(times): total -key count 1 if count K: break if count K: break return total def reset(self, playerId: int) - None: preScore self.scores[playerId] if self.sortedScores[-preScore] 1: del self.sortedScores[-preScore] else: self.sortedScores[-preScore] - 1 del self.scores[playerId]Java 版本class Leaderboard { MapInteger, Integer scores; TreeMapInteger, Integer sortedScores; public Leaderboard() { this.scores new HashMapInteger, Integer(); this.sortedScores new TreeMap(Collections.reverseOrder()); } public void addScore(int playerId, int score) { if (!this.scores.containsKey(playerId)) { this.scores.put(playerId, score); this.sortedScores.put(score, this.sortedScores.getOrDefault(score, 0) 1); } else { // 当前玩家分数变化需要更新 sortedScores旧分数计数减一。 int preScore this.scores.get(playerId); int playerCount this.sortedScores.get(preScore); // 若该分数已无人持有从树中移除。 if (playerCount 1) { this.sortedScores.remove(preScore); } else { this.sortedScores.put(preScore, playerCount - 1); } int newScore preScore score; this.scores.put(playerId, newScore); this.sortedScores.put(newScore, this.sortedScores.getOrDefault(newScore, 0) 1); } } public int top(int K) { int count 0; int sum 0; // 按 TreeMap 中分数降序遍历 for (Map.EntryInteger, Integer entry : this.sortedScores.entrySet()) { int times entry.getValue(); int key entry.getKey(); for (int i 0; i times; i) { sum key; count; if (count K) { break; } } if (count K) { break; } } return sum; } public void reset(int playerId) { int preScore this.scores.get(playerId); this.sortedScores.put(preScore, this.sortedScores.get(preScore) - 1); if (this.sortedScores.get(preScore) 0) { this.sortedScores.remove(preScore); } this.scores.remove(playerId); } }各语言「降序有序映射」的替代实现Cmapint, int, greaterint sortedScores通过第三个模板参数注入greater比较器无需取负技巧C#new SortedDictionaryint, int(Comparerint.Create((a, b) b.CompareTo(a)))自定义逆序比较器RustBTreeMapReversei32, i32Reverse包装器反转默认序KotlinTreeMapInt, Int(Collections.reverseOrder())与 Java 完全一致Go标准库没有有序 map文档实现了一个「scoreCount计数 map sortedScores降序切片」的组合用sort.Search做二分定位插入/删除位置findIndex、put、remove三个辅助方法是标准库受限时的典型手工模拟方案JavaScript / Swift标准库均无有序映射文档在top(K)中先取出全部键并排序JS 用[...keys()].sort((a, b) b - a)Swift 用keys.sorted(by: )再按人数累加——写入仍是 O(1) 计数但每次查询要 O(M log M)M 为不同分数个数排序。复杂度时间addScoreO(log N)resetO(log N)文档注明该复杂度在「每个玩家分数始终互不相同」的假设下成立此时有序映射规模为 N 量级topO(K)——前提是数据结构提供有序迭代器可以直接按序遍历并在凑满 K 个时停止若语言的标准库不提供自然迭代器如 JS、Swift 实现只能取出全部键值对另组有序列表文档指出这种情况下top会退化为O(N)空间O(N)scores字典占用若在top中新建全部键值对列表则额外 O(N)。三种方案横向对比操作方案一哈希表排序方案二最小堆方案三TreeMap/SortedMapaddScoreO(1)O(1)O(log N)resetO(1)O(1)O(log N)top(K)O(N log N)O(N log K)O(K)有自然迭代器时空间O(N)O(N K)O(N)选型建议写题或玩家规模小、top调用稀疏时方案一足够且最不易出错top频繁但 N 很大、K 明显小于 N 时方案二收益最大top极频繁且分数更新也频繁时方案三把查询压到 O(K) 是三者中最优的代价是每次写入多付出 O(log N) 并需要维护「双结构一致性」这一最容易出错的逻辑。常见陷阱文档最后专门总结了三个高频错误值得逐条对照检查。陷阱一reset到底是「删玩家」还是「置零」两种写法语义不同置零后玩家仍以 0 分留在表中会占据 Top-K 名额直接删除则玩家彻底不计入。取决于题目对reset的具体要求——本题各方案中方案一/二采用置零self.scores[playerId] 0方案三采用删除del self.scores[playerId]因为计数结构中「0 分玩家」没有意义# 方式 1分数置 0玩家仍以 0 分存在参与计算 def reset(self, playerId): self.scores[playerId] 0 # 方式 2彻底移除玩家对 TreeMap 方案更干净 def reset(self, playerId): del self.scores[playerId]陷阱二TreeMap 中忘记处理同分玩家有序映射里多个玩家可以同分必须存人数计数而不是单一玩家 ID否则第二个同分玩家会覆盖第一个# 错误每个分数只存一个玩家 self.sortedScores[score] playerId # 覆盖了前一个玩家 # 正确存每个分数对应的玩家数量 self.sortedScores[score] self.sortedScores.get(score, 0) 1陷阱三分数变化时只更新了一个结构addScore必须同步维护玩家映射与分数计数结构只改玩家分数、不回退旧分数计数就会留下脏数据导致top多算# 错误只更新玩家分数 def addScore(self, playerId, score): self.scores[playerId] self.scores.get(playerId, 0) score # 有序结构里旧分数的计数没有回退 # 正确两个结构都更新 def addScore(self, playerId, score): if playerId in self.scores: oldScore self.scores[playerId] self.sortedScores[oldScore] - 1 if self.sortedScores[oldScore] 0: del self.sortedScores[oldScore] newScore self.scores.get(playerId, 0) score self.scores[playerId] newScore self.sortedScores[newScore] self.sortedScores.get(newScore, 0) 1小结本文完整继承了 design-a-leaderboard.md 中暴力排序、K 容量最小堆、TreeMap 分数计数三种解法的直觉、算法步骤、多语言实现与复杂度分析并补充了三方案的性能对照表和选型依据。核心结论top查询的代价从 O(N log N) 一路压到 O(K) 的路径是「排序 → 堆 → 有序计数结构」而有序映射方案的全部易错点都集中在「分数变更时旧计数的回滚与删除」上三个常见陷阱恰好都围绕这一点。该文档的写作风格也符合 articles/README.md 中「至少覆盖一种与视频一致解法、给出时空复杂度、尽量覆盖所有相关解法」的仓库文章规范。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考