LeetCode 1086 High Five 高分五科平均分详解排序、最大堆与最小堆三种解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 articles/high-five.md 为核心系统讲解 LeetCode 1086「High Five」问题给定若干条[学生ID, 分数]记录求每名学生最高 5 次成绩的平均分向下取整。文章给出三种递进式解法——全局排序、Map 配合最大堆、Map 配合最小堆覆盖 Python、Java、C、JavaScript、Go、Kotlin、Swift、Rust 共 8 种语言的完整可运行实现并逐一分析直觉、算法步骤与时间复杂度读完即可在面试与刷题场景中灵活选用。前置知识在动手实现之前需要先掌握三个基础工具这也是本仓库 NeetCode 题解体系 中“数组与哈希 / 堆”类问题的通用能力自定义比较器排序Sorting with Custom Comparators——按多条件排序学生 ID 升序、分数降序哈希表Hash Maps——按 Key 分组将不同学生的分数按 ID 组织起来堆 / 优先队列Heaps / Priority Queues——用最小堆高效维护“前 K 大”元素或用最大堆直接取出最大的几个分数。问题模型与三种解法的总体思路给定二维数组items其中items[i] [student_id, score]每个学生至少有 5 条成绩但可能远多于 5 条。要求返回一个数组每个元素为[student_id, 该生最高5次成绩的平均值向下取整]且结果按学生 ID升序排列。围绕这一目标本文给出三条递进路线解法核心思想时间空间备注1. 排序先按(ID升序, 分数降序)全局排序再逐学生取前 5 条$O(N\log N)$$O(N)$最直观、易写2. Map 最大堆用堆保存每个学生的全部分数取时弹前 5 个最大值$O(N\log N)$$O(N)$天然满足“取最大”语义3. Map 最小堆堆容量恒定为 5超了就弹出最小值堆内即前 5 大$O(N\log N)$$O(N)$空间上最省只存每个学生的 Top 5其中 $N$ 为items的总条数。三种解法均满足“结果按 ID 升序”的要求解法一靠排序天然有序解法二/三靠遍历有序 MapTreeMap /sorted键序实现。解法一使用排序Using Sorting直觉目标等价于对每个学生取他分数降序排列后的前 5 个分数求均值。那么一个非常自然的做法就是——先把整张表按“ID 升序、同 ID 内分数降序”排好这样每个学生的前 5 条记录恰好就是他的最高 5 次成绩随后逐学生累加前 5 条并计算均值即可。算法步骤按学生 ID 升序排序ID 相同时按分数降序排序遍历排序后的数组一次处理一个学生对每个学生累加其前5条分数排序保证这 5 条即最高分跳过该学生剩余的分数这是本解法最容易遗漏的一步将[学生ID, 均值和 ÷ 5向下取整]写入结果返回结果数组。多语言实现class Solution: def highFive(self, items: List[List[int]]) - List[List[int]]: K 5 items.sort(keylambda x: (x[0], -x[1])) solution [] n len(items) i 0 while i n: id items[i][0] sum_val 0 for k in range(i, i K): sum_val items[k][1] while i n and items[i][0] id: i 1 solution.append([id, sum_val // K]) return solutionclass Solution { private int K; public int[][] highFive(int[][] items) { this.K 5; Arrays.sort( items, new Comparatorint[]() { Override public int compare(int[] a, int[] b) { if (a[0] ! b[0]) // item with lower id goes first return a[0] - b[0]; // in case of tie for ids, item with higher score goes first return b[1] - a[1]; } }); Listint[] solution new ArrayList(); int n items.length; int i 0; while (i n) { int id items[i][0]; int sum 0; // obtain total using the top 5 scores for (int k i; k i this.K; k) sum items[k][1]; // ignore all the other scores for the same id while (i n items[i][0] id) i; solution.add(new int[] {id, sum / this.K}); } int[][] solutionArray new int[solution.size()][]; return solution.toArray(solutionArray); } }class Solution { private: int K; public: vectorvectorint highFive(vectorvectorint items) { this-K 5; // sort items using the custom comparator sort(items.begin(), items.end(), [](const vectorint a, const vectorint b) { if (a[0] ! b[0]) // item with lower id goes first return a[0] b[0]; // in case of tie for ids, item with higher score goes first return a[1] b[1]; }); vectorvectorint solution; int n items.size(); int i 0; while (i n) { int id items[i][0]; int sum 0; // obtain total using the top 5 scores for (int k i; k i this-K; k) sum items[k][1]; // ignore all the other scores for the same id while (i n items[i][0] id) i; solution.push_back({id, sum / this-K}); } return solution; } };class Solution { /** * param {number[][]} items * return {number[][]} */ highFive(items) { const K 5; items.sort((a, b) { if (a[0] ! b[0]) return a[0] - b[0]; return b[1] - a[1]; }); const solution []; const n items.length; let i 0; while (i n) { const id items[i][0]; let sum 0; for (let k i; k i K; k) { sum items[k][1]; } while (i n items[i][0] id) { i; } solution.push([id, Math.floor(sum / K)]); } return solution; } }func highFive(items [][]int) [][]int { K : 5 sort.Slice(items, func(i, j int) bool { if items[i][0] ! items[j][0] { return items[i][0] items[j][0] } return items[i][1] items[j][1] }) solution : [][]int{} n : len(items) i : 0 for i n { id : items[i][0] sum : 0 for k : i; k iK; k { sum items[k][1] } for i n items[i][0] id { i } solution append(solution, []int{id, sum / K}) } return solution }class Solution { fun highFive(items: ArrayIntArray): ArrayIntArray { val K 5 items.sortWith(compareBy({ it[0] }, { -it[1] })) val solution mutableListOfIntArray() val n items.size var i 0 while (i n) { val id items[i][0] var sum 0 for (k in i until i K) { sum items[k][1] } while (i n items[i][0] id) { i } solution.add(intArrayOf(id, sum / K)) } return solution.toTypedArray() } }class Solution { func highFive(_ items: [[Int]]) - [[Int]] { let K 5 var sortedItems items.sorted { if $0[0] ! $1[0] { return $0[0] $1[0] } return $0[1] $1[1] } var solution [[Int]]() let n sortedItems.count var i 0 while i n { let id sortedItems[i][0] var sum 0 for k in i..(i K) { sum sortedItems[k][1] } while i n sortedItems[i][0] id { i 1 } solution.append([id, sum / K]) } return solution } }impl Solution { pub fn high_five(mut items: VecVeci32) - VecVeci32 { let k 5; items.sort_by(|a, b| { if a[0] ! b[0] { a[0].cmp(b[0]) } else { b[1].cmp(a[1]) } }); let mut solution Vec::new(); let n items.len(); let mut i 0; while i n { let id items[i][0]; let mut sum 0; for j in i..(i k) { sum items[j][1]; } while i n items[i][0] id { i 1; } solution.push(vec![id, sum / k as i32]); } solution } }实现要点剖析从源码可以看出各语言在“比较器”上的写法略有差异但语义完全一致第一关键字id升序第二关键字score降序。Python 用元组(x[0], -x[1])用取负号巧妙地让分数“降序”Java / C 在compare中对 ID 相同时返回b[1] - a[1]后项减前项即降序Rust 用b[1].cmp(a[1])体现“反向比较”Go 的sort.Slice回调返回布尔值逻辑为a[1] b[1]时认为a更小应排前。排序完成后内层for k in range(i, i K)累加前 5 条外层while items[i][0] id一次性跳过该学生剩余记录。这里必须使用while跳转而不是仅前移 5 格否则下一个学生会被错误地算进前一个学生的分组里。时间与空间复杂度时间复杂度$O(N \log N)$排序主导遍历累加是 $O(N)$空间复杂度$O(N)$排序在部分语言中需要额外空间如归并类排序结果数组本身也随学生数线性增长其中 $N$ 为items的总条数。解法二使用 Map 与最大堆Using Map and Max Heap直觉排序解法把“全表排序”作为前提而本题天然是一个分组取 Top K问题堆优先队列正是这类问题的经典结构。对每个学生维护一个最大堆最大的分数永远在堆顶连续弹出 5 次即可得到最高 5 次成绩。为了保证输出按 ID 升序Java 使用TreeMap、C 使用map、Rust 使用BTreeMap、其余语言在处理时先对键排序——本质都是“有序 Map”或“先收集再排序键”。算法步骤创建 MapKey 为学生 IDValue 为该学生的最大堆遍历所有items把每条分数推入对应学生的最大堆按学生 ID 的升序遍历 Map对每个学生从最大堆中弹出前5个分数并求和注意是弹出而非 peek将[学生ID, 均值]写入结果返回结果数组。多语言实现class Solution: def highFive(self, items: List[List[int]]) - List[List[int]]: K 5 all_scores defaultdict(list) for item in items: student_id item[0] score item[1] heapq.heappush(all_scores[student_id], -score) solution [] for student_id in sorted(all_scores.keys()): total 0 for i in range(K): total -heapq.heappop(all_scores[student_id]) solution.append([student_id, total // K]) return solutionclass Solution { private int K; public int[][] highFive(int[][] items) { this.K 5; TreeMapInteger, QueueInteger allScores new TreeMap(); for (int[] item : items) { int id item[0]; int score item[1]; if (!allScores.containsKey(id)) // max heap allScores.put(id, new PriorityQueue((a,b) - b - a)); // Add score to the max heap allScores.get(id).add(score); } Listint[] solution new ArrayList(); for (int id : allScores.keySet()) { int sum 0; // obtain the top k scores (k 5) for (int i 0; i this.K; i) sum allScores.get(id).poll(); solution.add(new int[] {id, sum / this.K}); } int[][] solutionArray new int[solution.size()][]; return solution.toArray(solutionArray); } }class Solution { private: int K; public: vectorvectorint highFive(vectorvectorint items) { this-K 5; mapint, priority_queueint allScores; for (const auto item: items) { int id item[0]; int score item[1]; // Add score to the max heap allScores[id].push(score); } vectorvectorint solution; for (auto [id, scores] : allScores) { int sum 0; // obtain the top k scores (k 5) for (int i 0; i this-K; i) { sum scores.top(); scores.pop(); } solution.push_back({id, sum / this-K}); } return solution; } };class Solution { /** * param {number[][]} items * return {number[][]} */ highFive(items) { const K 5; const allScores new Map(); for (const item of items) { const id item[0]; const score item[1]; if (!allScores.has(id)) { allScores.set(id, new MaxPriorityQueue()); } allScores.get(id).enqueue(score); } const solution []; const sortedIds Array.from(allScores.keys()).sort((a, b) a - b); for (const id of sortedIds) { let sum 0; const heap allScores.get(id); for (let i 0; i K; i) { sum heap.dequeue().element; } solution.push([id, Math.floor(sum / K)]); } return solution; } }type MaxHeap []int func (h MaxHeap) Len() int { return len(h) } func (h MaxHeap) Less(i, j int) bool { return h[i] h[j] } func (h MaxHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *MaxHeap) Push(x interface{}) { *h append(*h, x.(int)) } func (h *MaxHeap) Pop() interface{} { old : *h n : len(old) x : old[n-1] *h old[0 : n-1] return x } func highFive(items [][]int) [][]int { K : 5 allScores : make(map[int]*MaxHeap) for _, item : range items { id, score : item[0], item[1] if allScores[id] nil { allScores[id] MaxHeap{} heap.Init(allScores[id]) } heap.Push(allScores[id], score) } ids : make([]int, 0, len(allScores)) for id : range allScores { ids append(ids, id) } sort.Ints(ids) solution : [][]int{} for _, id : range ids { sum : 0 for i : 0; i K; i { sum heap.Pop(allScores[id]).(int) } solution append(solution, []int{id, sum / K}) } return solution }import java.util.PriorityQueue import java.util.TreeMap class Solution { fun highFive(items: ArrayIntArray): ArrayIntArray { val K 5 val allScores TreeMapInt, PriorityQueueInt() for (item in items) { val id item[0] val score item[1] if (!allScores.containsKey(id)) { allScores[id] PriorityQueue(compareByDescending { it }) } allScores[id]!!.add(score) } val solution mutableListOfIntArray() for (id in allScores.keys) { var sum 0 for (i in 0 until K) { sum allScores[id]!!.poll() } solution.add(intArrayOf(id, sum / K)) } return solution.toTypedArray() } }class Solution { func highFive(_ items: [[Int]]) - [[Int]] { let K 5 var allScores [Int: [Int]]() for item in items { let id item[0] let score item[1] if allScores[id] nil { allScores[id] [] } allScores[id]!.append(score) } var solution [[Int]]() for id in allScores.keys.sorted() { let scores allScores[id]!.sorted(by: ) var sum 0 for i in 0..K { sum scores[i] } solution.append([id, sum / K]) } return solution } }impl Solution { pub fn high_five(items: VecVeci32) - VecVeci32 { let k 5; let mut all_scores: BTreeMapi32, BinaryHeapi32 BTreeMap::new(); for item in items { let id item[0]; let score item[1]; all_scores.entry(id).or_insert_with(BinaryHeap::new).push(score); } let mut solution Vec::new(); for (id, scores) in mut all_scores { let mut sum 0; for _ in 0..k { sum scores.pop().unwrap(); } solution.push(vec![id, sum / k]); } solution } }实现要点剖析Python 的取巧写法标准库heapq只有最小堆于是用-score入堆、弹出时再取负还原等效实现最大堆Java / Kotlinnew PriorityQueue((a, b) - b - a)与compareByDescending { it }都是把默认的最小堆反转成最大堆C / Rustpriority_queueint与BinaryHeapi32本身就是最大堆无需额外配置Gocontainer/heap需要手动实现Len / Less / Swap / Push / Pop五个接口方法Less中h[i] h[j]即最大堆语义JavaScript依赖datastructures-js/priority-queue的MaxPriorityQueueenqueue入堆、dequeue().element取出最大值Swift语言无内建堆示例用“数组存全部分数 sorted(by: )取前 5”模拟最大堆效果思路等价。时间与空间复杂度时间复杂度$O(N \log N)$——每个分数入堆 $O(\log N)$ 一次、出堆至多 5 次/学生整体受堆操作与有序键遍历主导空间复杂度$O(N)$——Map 中保存了全部分数。其中 $N$ 为items的总条数。解法三使用 Map 与最小堆Using Map and Min Heap直觉解法二为每个学生保存了全部分数存在空间冗余。事实上我们只需要每个学生的Top 5。最小堆解法正是为此设计堆容量恒定为 5——新分数入堆后若堆大小超过 5就弹出堆顶当前最小元素。这样堆里永远只保留“当前见过的最大 5 个分数”结束时直接把堆内 5 个元素求和即可。相比解法二每个学生的堆只占用 5 个元素的固定空间。算法步骤创建 MapKey 为学生 IDValue 为该学生的最小堆对每条item把分数推入对应学生的最小堆若堆大小超过5弹出最小值维持堆内始终是 Top 5按学生 ID 升序遍历 Map对每个学生对堆内元素求和并计算均值返回结果数组。多语言实现class Solution: def highFive(self, items: List[List[int]]) - List[List[int]]: K 5 all_scores defaultdict(list) # Using defaultdict with list for min heap for item in items: student_id item[0] score item[1] heapq.heappush(all_scores[student_id], score) if len(all_scores[student_id]) K: heapq.heappop(all_scores[student_id]) solution [] for student_id in sorted(all_scores.keys()): total sum(all_scores[student_id]) solution.append([student_id, total // K]) return solutionclass Solution { private int K; public int[][] highFive(int[][] items) { this.K 5; TreeMapInteger, QueueInteger allScores new TreeMap(); for (int[] item : items) { int id item[0]; int score item[1]; if (!allScores.containsKey(id)) allScores.put(id, new PriorityQueue()); // insert the score in the min heap allScores.get(id).add(score); // remove the minimum element from the min heap in case the size of the min heap exceeds 5 if (allScores.get(id).size() this.K) allScores.get(id).poll(); } Listint[] solution new ArrayList(); for (int id : allScores.keySet()) { int sum 0; // min heap contains the top 5 scores for (int i 0; i this.K; i) sum allScores.get(id).poll(); solution.add(new int[] {id, sum / this.K}); } int[][] solutionArray new int[solution.size()][]; return solution.toArray(solutionArray); } }class Solution { private: int K; public: vectorvectorint highFive(vectorvectorint items) { this-K 5; mapint, priority_queueint, vectorint, greaterint allScores; for (const auto item: items) { int id item[0]; int score item[1]; // insert the score in the min heap allScores[id].push(score); // remove the minimum element from the min heap in case the size of the min heap exceeds 5 if (allScores[id].size() this-K) allScores[id].pop(); } vectorvectorint solution; for (auto [id, top_scores]: allScores) { int total 0; // min heap contains the top 5 scores for (int i 0; i this-K; i) { total top_scores.top(); top_scores.pop(); } solution.push_back({id, total / this-K}); } return solution; } };class Solution { /** * param {number[][]} items * return {number[][]} */ highFive(items) { const K 5; const allScores new Map(); for (const item of items) { const id item[0]; const score item[1]; if (!allScores.has(id)) { allScores.set(id, new MinPriorityQueue()); // Using { MinPriorityQueue } from datastructures-js/priority-queue; } allScores.get(id).enqueue(score); if (allScores.get(id).size() K) { allScores.get(id).dequeue(); } } const solution []; const sortedIds Array.from(allScores.keys()).sort((a, b) a - b); for (const id of sortedIds) { let sum 0; const heap allScores.get(id); for (let i 0; i K; i) { sum heap.dequeue().element; } solution.push([id, Math.floor(sum / K)]); } return solution; } }type MinHeap []int func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Less(i, j int) bool { return h[i] h[j] } func (h MinHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *MinHeap) Push(x interface{}) { *h append(*h, x.(int)) } func (h *MinHeap) Pop() interface{} { old : *h n : len(old) x : old[n-1] *h old[0 : n-1] return x } func highFive(items [][]int) [][]int { K : 5 allScores : make(map[int]*MinHeap) for _, item : range items { id, score : item[0], item[1] if allScores[id] nil { allScores[id] MinHeap{} heap.Init(allScores[id]) } heap.Push(allScores[id], score) if allScores[id].Len() K { heap.Pop(allScores[id]) } } ids : make([]int, 0, len(allScores)) for id : range allScores { ids append(ids, id) } sort.Ints(ids) solution : [][]int{} for _, id : range ids { sum : 0 for allScores[id].Len() 0 { sum heap.Pop(allScores[id]).(int) } solution append(solution, []int{id, sum / K}) } return solution }import java.util.PriorityQueue import java.util.TreeMap class Solution { fun highFive(items: ArrayIntArray): ArrayIntArray { val K 5 val allScores TreeMapInt, PriorityQueueInt() for (item in items) { val id item[0] val score item[1] if (!allScores.containsKey(id)) { allScores[id] PriorityQueue() } allScores[id]!!.add(score) if (allScores[id]!!.size K) { allScores[id]!!.poll() } } val solution mutableListOfIntArray() for (id in allScores.keys) { var sum 0 for (i in 0 until K) { sum allScores[id]!!.poll() } solution.add(intArrayOf(id, sum / K)) } return solution.toTypedArray() } }class Solution { func highFive(_ items: [[Int]]) - [[Int]] { let K 5 var allScores [Int: [Int]]() for item in items { let id item[0] let score item[1] if allScores[id] nil { allScores[id] [] } allScores[id]!.append(score) allScores[id]!.sort() if allScores[id]!.count K { allScores[id]!.removeFirst() } } var solution [[Int]]() for id in allScores.keys.sorted() { let total allScores[id]!.reduce(0, ) solution.append([id, total / K]) } return solution } }impl Solution { pub fn high_five(items: VecVeci32) - VecVeci32 { let k 5; let mut all_scores: BTreeMapi32, BinaryHeapReversei32 BTreeMap::new(); for item in items { let id item[0]; let score item[1]; let heap all_scores.entry(id).or_insert_with(BinaryHeap::new); heap.push(Reverse(score)); if heap.len() k { heap.pop(); } } let mut solution Vec::new(); for (id, scores) in all_scores { let total: i32 scores.iter().map(|Reverse(s)| s).sum(); solution.push(vec![id, total / k as i32]); } solution } }实现要点剖析默认最小堆的语言Pythonheapq、Java/KotlinPriorityQueue、Cpriority_queue..., greaterint、GoMinHeap、JSMinPriorityQueue直接复用默认语义Rust 的BinaryHeap是最大堆因此用Reverse(score)包裹后再入堆等效出最小堆heap.len() k时pop()掉的是“反向后的最小”即原始分数中的最小值Swift 用“数组 每次sort()removeFirst()”模拟容量为 5 的最小堆直观且空间固定注意最终的求和方式Python 用sum(all_scores[student_id])此时堆内恰好 5 个元素Go 用for allScores[id].Len() 0清空求和两者殊途同归。时间与空间复杂度时间复杂度$O(N \log N)$——每次入堆 $O(\log 5)$可视为常数整体由遍历与有序键处理决定仍记为 $O(N \log N)$空间复杂度$O(N)$——但每个学生的堆最多只有5个元素实际占用比解法二更小。其中 $N$ 为items的总条数。常见陷阱Common Pitfalls陷阱一假设每个学生恰好只有 5 条分数题目保证每个学生至少有 5 条成绩但可能更多。最常见的错误是“只处理 5 条就收工”却没有正确跳过该学生的剩余分数排序解法对每个学生累加完前 5 条后必须用while跳过同 ID 的其余记录对应代码中的while i n and items[i][0] id: i 1堆解法无论堆里实际有多少元素只提取恰好 5 个——最小堆解法通过“超 5 弹最小”提前保证堆内恰好 5 个最大堆解法则是弹出 5 次后不再弹出。陷阱二用错堆的类型最小堆解法依赖“保留 Top 5、剔除最小值”这一机制这是整个算法的正确性核心如果误用最大堆做“容量 5”方案每次超过 5 个时弹出的是最大值堆里反而留下的是最小的几个分数结果完全错误同样最大堆解法中要确保是弹出pop/poll/dequeue而不是只看堆顶peek——只看不弹5 次拿到的都是同一个最大值。三种解法如何选择维度解法一排序解法二Map 最大堆解法三Map 最小堆直觉难度最低中等中等需理解“容量 5 淘汰最小”代码量最少中等中等空间占用$O(N)$$O(N)$存全部分数每个学生固定 5 个元素适用场景面试首选简洁易懂强调“取最大”语义数据量大、追求空间效率时本题在 articles/high-five.md 中给出了三种方案在 8 种语言下的完整实现可作为多语言对照模板直接复用。仓库的 articles/README.md 进一步说明了本仓库文章规范至少包含一种与 NeetCode 视频相近的解法、给出时间与空间复杂度、尽量覆盖全部相关解法本篇文章正是按此规范组织三种思路覆盖了“排序 → 最大堆 → 容量受限最小堆”的完整进阶路径无论面试追问哪种变体如把5换成任意K、或要求流式处理都能基于这三块积木快速作答。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 1086 High Five 高分五科平均分详解：排序、最大堆与最小堆三种解法
LeetCode 1086 High Five 高分五科平均分详解排序、最大堆与最小堆三种解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 articles/high-five.md 为核心系统讲解 LeetCode 1086「High Five」问题给定若干条[学生ID, 分数]记录求每名学生最高 5 次成绩的平均分向下取整。文章给出三种递进式解法——全局排序、Map 配合最大堆、Map 配合最小堆覆盖 Python、Java、C、JavaScript、Go、Kotlin、Swift、Rust 共 8 种语言的完整可运行实现并逐一分析直觉、算法步骤与时间复杂度读完即可在面试与刷题场景中灵活选用。前置知识在动手实现之前需要先掌握三个基础工具这也是本仓库 NeetCode 题解体系 中“数组与哈希 / 堆”类问题的通用能力自定义比较器排序Sorting with Custom Comparators——按多条件排序学生 ID 升序、分数降序哈希表Hash Maps——按 Key 分组将不同学生的分数按 ID 组织起来堆 / 优先队列Heaps / Priority Queues——用最小堆高效维护“前 K 大”元素或用最大堆直接取出最大的几个分数。问题模型与三种解法的总体思路给定二维数组items其中items[i] [student_id, score]每个学生至少有 5 条成绩但可能远多于 5 条。要求返回一个数组每个元素为[student_id, 该生最高5次成绩的平均值向下取整]且结果按学生 ID升序排列。围绕这一目标本文给出三条递进路线解法核心思想时间空间备注1. 排序先按(ID升序, 分数降序)全局排序再逐学生取前 5 条$O(N\log N)$$O(N)$最直观、易写2. Map 最大堆用堆保存每个学生的全部分数取时弹前 5 个最大值$O(N\log N)$$O(N)$天然满足“取最大”语义3. Map 最小堆堆容量恒定为 5超了就弹出最小值堆内即前 5 大$O(N\log N)$$O(N)$空间上最省只存每个学生的 Top 5其中 $N$ 为items的总条数。三种解法均满足“结果按 ID 升序”的要求解法一靠排序天然有序解法二/三靠遍历有序 MapTreeMap /sorted键序实现。解法一使用排序Using Sorting直觉目标等价于对每个学生取他分数降序排列后的前 5 个分数求均值。那么一个非常自然的做法就是——先把整张表按“ID 升序、同 ID 内分数降序”排好这样每个学生的前 5 条记录恰好就是他的最高 5 次成绩随后逐学生累加前 5 条并计算均值即可。算法步骤按学生 ID 升序排序ID 相同时按分数降序排序遍历排序后的数组一次处理一个学生对每个学生累加其前5条分数排序保证这 5 条即最高分跳过该学生剩余的分数这是本解法最容易遗漏的一步将[学生ID, 均值和 ÷ 5向下取整]写入结果返回结果数组。多语言实现class Solution: def highFive(self, items: List[List[int]]) - List[List[int]]: K 5 items.sort(keylambda x: (x[0], -x[1])) solution [] n len(items) i 0 while i n: id items[i][0] sum_val 0 for k in range(i, i K): sum_val items[k][1] while i n and items[i][0] id: i 1 solution.append([id, sum_val // K]) return solutionclass Solution { private int K; public int[][] highFive(int[][] items) { this.K 5; Arrays.sort( items, new Comparatorint[]() { Override public int compare(int[] a, int[] b) { if (a[0] ! b[0]) // item with lower id goes first return a[0] - b[0]; // in case of tie for ids, item with higher score goes first return b[1] - a[1]; } }); Listint[] solution new ArrayList(); int n items.length; int i 0; while (i n) { int id items[i][0]; int sum 0; // obtain total using the top 5 scores for (int k i; k i this.K; k) sum items[k][1]; // ignore all the other scores for the same id while (i n items[i][0] id) i; solution.add(new int[] {id, sum / this.K}); } int[][] solutionArray new int[solution.size()][]; return solution.toArray(solutionArray); } }class Solution { private: int K; public: vectorvectorint highFive(vectorvectorint items) { this-K 5; // sort items using the custom comparator sort(items.begin(), items.end(), [](const vectorint a, const vectorint b) { if (a[0] ! b[0]) // item with lower id goes first return a[0] b[0]; // in case of tie for ids, item with higher score goes first return a[1] b[1]; }); vectorvectorint solution; int n items.size(); int i 0; while (i n) { int id items[i][0]; int sum 0; // obtain total using the top 5 scores for (int k i; k i this-K; k) sum items[k][1]; // ignore all the other scores for the same id while (i n items[i][0] id) i; solution.push_back({id, sum / this-K}); } return solution; } };class Solution { /** * param {number[][]} items * return {number[][]} */ highFive(items) { const K 5; items.sort((a, b) { if (a[0] ! b[0]) return a[0] - b[0]; return b[1] - a[1]; }); const solution []; const n items.length; let i 0; while (i n) { const id items[i][0]; let sum 0; for (let k i; k i K; k) { sum items[k][1]; } while (i n items[i][0] id) { i; } solution.push([id, Math.floor(sum / K)]); } return solution; } }func highFive(items [][]int) [][]int { K : 5 sort.Slice(items, func(i, j int) bool { if items[i][0] ! items[j][0] { return items[i][0] items[j][0] } return items[i][1] items[j][1] }) solution : [][]int{} n : len(items) i : 0 for i n { id : items[i][0] sum : 0 for k : i; k iK; k { sum items[k][1] } for i n items[i][0] id { i } solution append(solution, []int{id, sum / K}) } return solution }class Solution { fun highFive(items: ArrayIntArray): ArrayIntArray { val K 5 items.sortWith(compareBy({ it[0] }, { -it[1] })) val solution mutableListOfIntArray() val n items.size var i 0 while (i n) { val id items[i][0] var sum 0 for (k in i until i K) { sum items[k][1] } while (i n items[i][0] id) { i } solution.add(intArrayOf(id, sum / K)) } return solution.toTypedArray() } }class Solution { func highFive(_ items: [[Int]]) - [[Int]] { let K 5 var sortedItems items.sorted { if $0[0] ! $1[0] { return $0[0] $1[0] } return $0[1] $1[1] } var solution [[Int]]() let n sortedItems.count var i 0 while i n { let id sortedItems[i][0] var sum 0 for k in i..(i K) { sum sortedItems[k][1] } while i n sortedItems[i][0] id { i 1 } solution.append([id, sum / K]) } return solution } }impl Solution { pub fn high_five(mut items: VecVeci32) - VecVeci32 { let k 5; items.sort_by(|a, b| { if a[0] ! b[0] { a[0].cmp(b[0]) } else { b[1].cmp(a[1]) } }); let mut solution Vec::new(); let n items.len(); let mut i 0; while i n { let id items[i][0]; let mut sum 0; for j in i..(i k) { sum items[j][1]; } while i n items[i][0] id { i 1; } solution.push(vec![id, sum / k as i32]); } solution } }实现要点剖析从源码可以看出各语言在“比较器”上的写法略有差异但语义完全一致第一关键字id升序第二关键字score降序。Python 用元组(x[0], -x[1])用取负号巧妙地让分数“降序”Java / C 在compare中对 ID 相同时返回b[1] - a[1]后项减前项即降序Rust 用b[1].cmp(a[1])体现“反向比较”Go 的sort.Slice回调返回布尔值逻辑为a[1] b[1]时认为a更小应排前。排序完成后内层for k in range(i, i K)累加前 5 条外层while items[i][0] id一次性跳过该学生剩余记录。这里必须使用while跳转而不是仅前移 5 格否则下一个学生会被错误地算进前一个学生的分组里。时间与空间复杂度时间复杂度$O(N \log N)$排序主导遍历累加是 $O(N)$空间复杂度$O(N)$排序在部分语言中需要额外空间如归并类排序结果数组本身也随学生数线性增长其中 $N$ 为items的总条数。解法二使用 Map 与最大堆Using Map and Max Heap直觉排序解法把“全表排序”作为前提而本题天然是一个分组取 Top K问题堆优先队列正是这类问题的经典结构。对每个学生维护一个最大堆最大的分数永远在堆顶连续弹出 5 次即可得到最高 5 次成绩。为了保证输出按 ID 升序Java 使用TreeMap、C 使用map、Rust 使用BTreeMap、其余语言在处理时先对键排序——本质都是“有序 Map”或“先收集再排序键”。算法步骤创建 MapKey 为学生 IDValue 为该学生的最大堆遍历所有items把每条分数推入对应学生的最大堆按学生 ID 的升序遍历 Map对每个学生从最大堆中弹出前5个分数并求和注意是弹出而非 peek将[学生ID, 均值]写入结果返回结果数组。多语言实现class Solution: def highFive(self, items: List[List[int]]) - List[List[int]]: K 5 all_scores defaultdict(list) for item in items: student_id item[0] score item[1] heapq.heappush(all_scores[student_id], -score) solution [] for student_id in sorted(all_scores.keys()): total 0 for i in range(K): total -heapq.heappop(all_scores[student_id]) solution.append([student_id, total // K]) return solutionclass Solution { private int K; public int[][] highFive(int[][] items) { this.K 5; TreeMapInteger, QueueInteger allScores new TreeMap(); for (int[] item : items) { int id item[0]; int score item[1]; if (!allScores.containsKey(id)) // max heap allScores.put(id, new PriorityQueue((a,b) - b - a)); // Add score to the max heap allScores.get(id).add(score); } Listint[] solution new ArrayList(); for (int id : allScores.keySet()) { int sum 0; // obtain the top k scores (k 5) for (int i 0; i this.K; i) sum allScores.get(id).poll(); solution.add(new int[] {id, sum / this.K}); } int[][] solutionArray new int[solution.size()][]; return solution.toArray(solutionArray); } }class Solution { private: int K; public: vectorvectorint highFive(vectorvectorint items) { this-K 5; mapint, priority_queueint allScores; for (const auto item: items) { int id item[0]; int score item[1]; // Add score to the max heap allScores[id].push(score); } vectorvectorint solution; for (auto [id, scores] : allScores) { int sum 0; // obtain the top k scores (k 5) for (int i 0; i this-K; i) { sum scores.top(); scores.pop(); } solution.push_back({id, sum / this-K}); } return solution; } };class Solution { /** * param {number[][]} items * return {number[][]} */ highFive(items) { const K 5; const allScores new Map(); for (const item of items) { const id item[0]; const score item[1]; if (!allScores.has(id)) { allScores.set(id, new MaxPriorityQueue()); } allScores.get(id).enqueue(score); } const solution []; const sortedIds Array.from(allScores.keys()).sort((a, b) a - b); for (const id of sortedIds) { let sum 0; const heap allScores.get(id); for (let i 0; i K; i) { sum heap.dequeue().element; } solution.push([id, Math.floor(sum / K)]); } return solution; } }type MaxHeap []int func (h MaxHeap) Len() int { return len(h) } func (h MaxHeap) Less(i, j int) bool { return h[i] h[j] } func (h MaxHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *MaxHeap) Push(x interface{}) { *h append(*h, x.(int)) } func (h *MaxHeap) Pop() interface{} { old : *h n : len(old) x : old[n-1] *h old[0 : n-1] return x } func highFive(items [][]int) [][]int { K : 5 allScores : make(map[int]*MaxHeap) for _, item : range items { id, score : item[0], item[1] if allScores[id] nil { allScores[id] MaxHeap{} heap.Init(allScores[id]) } heap.Push(allScores[id], score) } ids : make([]int, 0, len(allScores)) for id : range allScores { ids append(ids, id) } sort.Ints(ids) solution : [][]int{} for _, id : range ids { sum : 0 for i : 0; i K; i { sum heap.Pop(allScores[id]).(int) } solution append(solution, []int{id, sum / K}) } return solution }import java.util.PriorityQueue import java.util.TreeMap class Solution { fun highFive(items: ArrayIntArray): ArrayIntArray { val K 5 val allScores TreeMapInt, PriorityQueueInt() for (item in items) { val id item[0] val score item[1] if (!allScores.containsKey(id)) { allScores[id] PriorityQueue(compareByDescending { it }) } allScores[id]!!.add(score) } val solution mutableListOfIntArray() for (id in allScores.keys) { var sum 0 for (i in 0 until K) { sum allScores[id]!!.poll() } solution.add(intArrayOf(id, sum / K)) } return solution.toTypedArray() } }class Solution { func highFive(_ items: [[Int]]) - [[Int]] { let K 5 var allScores [Int: [Int]]() for item in items { let id item[0] let score item[1] if allScores[id] nil { allScores[id] [] } allScores[id]!.append(score) } var solution [[Int]]() for id in allScores.keys.sorted() { let scores allScores[id]!.sorted(by: ) var sum 0 for i in 0..K { sum scores[i] } solution.append([id, sum / K]) } return solution } }impl Solution { pub fn high_five(items: VecVeci32) - VecVeci32 { let k 5; let mut all_scores: BTreeMapi32, BinaryHeapi32 BTreeMap::new(); for item in items { let id item[0]; let score item[1]; all_scores.entry(id).or_insert_with(BinaryHeap::new).push(score); } let mut solution Vec::new(); for (id, scores) in mut all_scores { let mut sum 0; for _ in 0..k { sum scores.pop().unwrap(); } solution.push(vec![id, sum / k]); } solution } }实现要点剖析Python 的取巧写法标准库heapq只有最小堆于是用-score入堆、弹出时再取负还原等效实现最大堆Java / Kotlinnew PriorityQueue((a, b) - b - a)与compareByDescending { it }都是把默认的最小堆反转成最大堆C / Rustpriority_queueint与BinaryHeapi32本身就是最大堆无需额外配置Gocontainer/heap需要手动实现Len / Less / Swap / Push / Pop五个接口方法Less中h[i] h[j]即最大堆语义JavaScript依赖datastructures-js/priority-queue的MaxPriorityQueueenqueue入堆、dequeue().element取出最大值Swift语言无内建堆示例用“数组存全部分数 sorted(by: )取前 5”模拟最大堆效果思路等价。时间与空间复杂度时间复杂度$O(N \log N)$——每个分数入堆 $O(\log N)$ 一次、出堆至多 5 次/学生整体受堆操作与有序键遍历主导空间复杂度$O(N)$——Map 中保存了全部分数。其中 $N$ 为items的总条数。解法三使用 Map 与最小堆Using Map and Min Heap直觉解法二为每个学生保存了全部分数存在空间冗余。事实上我们只需要每个学生的Top 5。最小堆解法正是为此设计堆容量恒定为 5——新分数入堆后若堆大小超过 5就弹出堆顶当前最小元素。这样堆里永远只保留“当前见过的最大 5 个分数”结束时直接把堆内 5 个元素求和即可。相比解法二每个学生的堆只占用 5 个元素的固定空间。算法步骤创建 MapKey 为学生 IDValue 为该学生的最小堆对每条item把分数推入对应学生的最小堆若堆大小超过5弹出最小值维持堆内始终是 Top 5按学生 ID 升序遍历 Map对每个学生对堆内元素求和并计算均值返回结果数组。多语言实现class Solution: def highFive(self, items: List[List[int]]) - List[List[int]]: K 5 all_scores defaultdict(list) # Using defaultdict with list for min heap for item in items: student_id item[0] score item[1] heapq.heappush(all_scores[student_id], score) if len(all_scores[student_id]) K: heapq.heappop(all_scores[student_id]) solution [] for student_id in sorted(all_scores.keys()): total sum(all_scores[student_id]) solution.append([student_id, total // K]) return solutionclass Solution { private int K; public int[][] highFive(int[][] items) { this.K 5; TreeMapInteger, QueueInteger allScores new TreeMap(); for (int[] item : items) { int id item[0]; int score item[1]; if (!allScores.containsKey(id)) allScores.put(id, new PriorityQueue()); // insert the score in the min heap allScores.get(id).add(score); // remove the minimum element from the min heap in case the size of the min heap exceeds 5 if (allScores.get(id).size() this.K) allScores.get(id).poll(); } Listint[] solution new ArrayList(); for (int id : allScores.keySet()) { int sum 0; // min heap contains the top 5 scores for (int i 0; i this.K; i) sum allScores.get(id).poll(); solution.add(new int[] {id, sum / this.K}); } int[][] solutionArray new int[solution.size()][]; return solution.toArray(solutionArray); } }class Solution { private: int K; public: vectorvectorint highFive(vectorvectorint items) { this-K 5; mapint, priority_queueint, vectorint, greaterint allScores; for (const auto item: items) { int id item[0]; int score item[1]; // insert the score in the min heap allScores[id].push(score); // remove the minimum element from the min heap in case the size of the min heap exceeds 5 if (allScores[id].size() this-K) allScores[id].pop(); } vectorvectorint solution; for (auto [id, top_scores]: allScores) { int total 0; // min heap contains the top 5 scores for (int i 0; i this-K; i) { total top_scores.top(); top_scores.pop(); } solution.push_back({id, total / this-K}); } return solution; } };class Solution { /** * param {number[][]} items * return {number[][]} */ highFive(items) { const K 5; const allScores new Map(); for (const item of items) { const id item[0]; const score item[1]; if (!allScores.has(id)) { allScores.set(id, new MinPriorityQueue()); // Using { MinPriorityQueue } from datastructures-js/priority-queue; } allScores.get(id).enqueue(score); if (allScores.get(id).size() K) { allScores.get(id).dequeue(); } } const solution []; const sortedIds Array.from(allScores.keys()).sort((a, b) a - b); for (const id of sortedIds) { let sum 0; const heap allScores.get(id); for (let i 0; i K; i) { sum heap.dequeue().element; } solution.push([id, Math.floor(sum / K)]); } return solution; } }type MinHeap []int func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Less(i, j int) bool { return h[i] h[j] } func (h MinHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *MinHeap) Push(x interface{}) { *h append(*h, x.(int)) } func (h *MinHeap) Pop() interface{} { old : *h n : len(old) x : old[n-1] *h old[0 : n-1] return x } func highFive(items [][]int) [][]int { K : 5 allScores : make(map[int]*MinHeap) for _, item : range items { id, score : item[0], item[1] if allScores[id] nil { allScores[id] MinHeap{} heap.Init(allScores[id]) } heap.Push(allScores[id], score) if allScores[id].Len() K { heap.Pop(allScores[id]) } } ids : make([]int, 0, len(allScores)) for id : range allScores { ids append(ids, id) } sort.Ints(ids) solution : [][]int{} for _, id : range ids { sum : 0 for allScores[id].Len() 0 { sum heap.Pop(allScores[id]).(int) } solution append(solution, []int{id, sum / K}) } return solution }import java.util.PriorityQueue import java.util.TreeMap class Solution { fun highFive(items: ArrayIntArray): ArrayIntArray { val K 5 val allScores TreeMapInt, PriorityQueueInt() for (item in items) { val id item[0] val score item[1] if (!allScores.containsKey(id)) { allScores[id] PriorityQueue() } allScores[id]!!.add(score) if (allScores[id]!!.size K) { allScores[id]!!.poll() } } val solution mutableListOfIntArray() for (id in allScores.keys) { var sum 0 for (i in 0 until K) { sum allScores[id]!!.poll() } solution.add(intArrayOf(id, sum / K)) } return solution.toTypedArray() } }class Solution { func highFive(_ items: [[Int]]) - [[Int]] { let K 5 var allScores [Int: [Int]]() for item in items { let id item[0] let score item[1] if allScores[id] nil { allScores[id] [] } allScores[id]!.append(score) allScores[id]!.sort() if allScores[id]!.count K { allScores[id]!.removeFirst() } } var solution [[Int]]() for id in allScores.keys.sorted() { let total allScores[id]!.reduce(0, ) solution.append([id, total / K]) } return solution } }impl Solution { pub fn high_five(items: VecVeci32) - VecVeci32 { let k 5; let mut all_scores: BTreeMapi32, BinaryHeapReversei32 BTreeMap::new(); for item in items { let id item[0]; let score item[1]; let heap all_scores.entry(id).or_insert_with(BinaryHeap::new); heap.push(Reverse(score)); if heap.len() k { heap.pop(); } } let mut solution Vec::new(); for (id, scores) in all_scores { let total: i32 scores.iter().map(|Reverse(s)| s).sum(); solution.push(vec![id, total / k as i32]); } solution } }实现要点剖析默认最小堆的语言Pythonheapq、Java/KotlinPriorityQueue、Cpriority_queue..., greaterint、GoMinHeap、JSMinPriorityQueue直接复用默认语义Rust 的BinaryHeap是最大堆因此用Reverse(score)包裹后再入堆等效出最小堆heap.len() k时pop()掉的是“反向后的最小”即原始分数中的最小值Swift 用“数组 每次sort()removeFirst()”模拟容量为 5 的最小堆直观且空间固定注意最终的求和方式Python 用sum(all_scores[student_id])此时堆内恰好 5 个元素Go 用for allScores[id].Len() 0清空求和两者殊途同归。时间与空间复杂度时间复杂度$O(N \log N)$——每次入堆 $O(\log 5)$可视为常数整体由遍历与有序键处理决定仍记为 $O(N \log N)$空间复杂度$O(N)$——但每个学生的堆最多只有5个元素实际占用比解法二更小。其中 $N$ 为items的总条数。常见陷阱Common Pitfalls陷阱一假设每个学生恰好只有 5 条分数题目保证每个学生至少有 5 条成绩但可能更多。最常见的错误是“只处理 5 条就收工”却没有正确跳过该学生的剩余分数排序解法对每个学生累加完前 5 条后必须用while跳过同 ID 的其余记录对应代码中的while i n and items[i][0] id: i 1堆解法无论堆里实际有多少元素只提取恰好 5 个——最小堆解法通过“超 5 弹最小”提前保证堆内恰好 5 个最大堆解法则是弹出 5 次后不再弹出。陷阱二用错堆的类型最小堆解法依赖“保留 Top 5、剔除最小值”这一机制这是整个算法的正确性核心如果误用最大堆做“容量 5”方案每次超过 5 个时弹出的是最大值堆里反而留下的是最小的几个分数结果完全错误同样最大堆解法中要确保是弹出pop/poll/dequeue而不是只看堆顶peek——只看不弹5 次拿到的都是同一个最大值。三种解法如何选择维度解法一排序解法二Map 最大堆解法三Map 最小堆直觉难度最低中等中等需理解“容量 5 淘汰最小”代码量最少中等中等空间占用$O(N)$$O(N)$存全部分数每个学生固定 5 个元素适用场景面试首选简洁易懂强调“取最大”语义数据量大、追求空间效率时本题在 articles/high-five.md 中给出了三种方案在 8 种语言下的完整实现可作为多语言对照模板直接复用。仓库的 articles/README.md 进一步说明了本仓库文章规范至少包含一种与 NeetCode 视频相近的解法、给出时间与空间复杂度、尽量覆盖全部相关解法本篇文章正是按此规范组织三种思路覆盖了“排序 → 最大堆 → 容量受限最小堆”的完整进阶路径无论面试追问哪种变体如把5换成任意K、或要求流式处理都能基于这三块积木快速作答。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考