企业官网建设流程全解析

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升序排列。

围绕这一目标，本文给出三条递进路线：

其中 $N$ 为items的总条数。三种解法均满足“结果按 ID 升序”的要求：解法一靠排序天然有序，解法二/三靠遍历有序 Map（TreeMap /sorted键序）实现。

解法一：使用排序（Using Sorting）

直觉

目标等价于：对每个学生，取他分数降序排列后的前 5 个分数求均值。那么一个非常自然的做法就是——先把整张表按“ID 升序、同 ID 内分数降序”排好，这样每个学生的前 5 条记录恰好就是他的最高 5 次成绩；随后逐学生累加前 5 条并计算均值即可。

算法步骤

1. 按学生 ID 升序排序；ID 相同时按分数降序排序；
2. 遍历排序后的数组，一次处理一个学生；
3. 对每个学生，累加其前5条分数（排序保证这 5 条即最高分）；
4. 跳过该学生剩余的分数（这是本解法最容易遗漏的一步）；
5. 将[学生ID, 均值（和 ÷ 5，向下取整）]写入结果；
6. 返回结果数组。

多语言实现

class Solution: def highFive(self, items: List[List[int]]) -> List[List[int]]: K = 5 items.sort(key=lambda 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 solution

class Solution { private int K; public int[][] highFive(int[][] items) { this.K = 5; Arrays.sort( items, new Comparator<int[]>() { @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]; } }); List<int[]> 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: vector<vector<int>> highFive(vector<vector<int>>& items) { this->K = 5; // sort items using the custom comparator sort(items.begin(), items.end(), [](const vector<int> &a, const vector<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 a[1] > b[1]; }); vector<vector<int>> 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 < i+K; 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: Array<IntArray>): Array<IntArray> { val K = 5 items.sortWith(compareBy({ it[0] }, { -it[1] })) val solution = mutableListOf<IntArray>() 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: Vec<Vec<i32>>) -> Vec<Vec<i32>> { 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”或“先收集再排序键”。

算法步骤

1. 创建 Map：Key 为学生 ID，Value 为该学生的最大堆；
2. 遍历所有items，把每条分数推入对应学生的最大堆；
3. 按学生 ID 的升序遍历 Map；
4. 对每个学生，从最大堆中弹出前5个分数并求和（注意是弹出而非 peek）；
5. 将[学生ID, 均值]写入结果；
6. 返回结果数组。

多语言实现

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 solution

class Solution { private int K; public int[][] highFive(int[][] items) { this.K = 5; TreeMap<Integer, Queue<Integer>> 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); } List<int[]> 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: vector<vector<int>> highFive(vector<vector<int>>& items) { this->K = 5; map<int, priority_queue<int>> allScores; for (const auto &item: items) { int id = item[0]; int score = item[1]; // Add score to the max heap allScores[id].push(score); } vector<vector<int>> 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: Array<IntArray>): Array<IntArray> { val K = 5 val allScores = TreeMap<Int, PriorityQueue<Int>>() 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 = mutableListOf<IntArray>() 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: Vec<Vec<i32>>) -> Vec<Vec<i32>> { let k = 5; let mut all_scores: BTreeMap<i32, BinaryHeap<i32>> = 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 / Kotlin：new PriorityQueue<>((a, b) -> b - a)与compareByDescending { it }都是把默认的最小堆反转成最大堆；
• C++ / Rust：priority_queue<int>与BinaryHeap<i32>本身就是最大堆，无需额外配置；
• Go：container/heap需要手动实现Len / Less / Swap / Push / Pop五个接口方法，Less中h[i] > h[j]即最大堆语义；
• JavaScript：依赖@datastructures-js/priority-queue的MaxPriorityQueue（enqueue入堆、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 个元素的固定空间。

算法步骤

1. 创建 Map：Key 为学生 ID，Value 为该学生的最小堆；
2. 对每条item，把分数推入对应学生的最小堆；
3. 若堆大小超过5，弹出最小值，维持堆内始终是 Top 5；
4. 按学生 ID 升序遍历 Map；
5. 对每个学生，对堆内元素求和并计算均值；
6. 返回结果数组。

多语言实现

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 solution

class Solution { private int K; public int[][] highFive(int[][] items) { this.K = 5; TreeMap<Integer, Queue<Integer>> 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(); } List<int[]> 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: vector<vector<int>> highFive(vector<vector<int>>& items) { this->K = 5; map<int, priority_queue<int, vector<int>, greater<int>>> 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(); } vector<vector<int>> 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: Array<IntArray>): Array<IntArray> { val K = 5 val allScores = TreeMap<Int, PriorityQueue<Int>>() 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 = mutableListOf<IntArray>() 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: Vec<Vec<i32>>) -> Vec<Vec<i32>> { let k = 5; let mut all_scores: BTreeMap<i32, BinaryHeap<Reverse<i32>>> = 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、C++priority_queue<..., greater<int>>、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 次拿到的都是同一个最大值。

三种解法如何选择

本题在 articles/high-five.md 中给出了三种方案在 8 种语言下的完整实现，可作为多语言对照模板直接复用。仓库的 articles/README.md 进一步说明了本仓库文章规范（至少包含一种与 NeetCode 视频相近的解法、给出时间与空间复杂度、尽量覆盖全部相关解法），本篇文章正是按此规范组织：三种思路覆盖了“排序 → 最大堆 → 容量受限最小堆”的完整进阶路径，无论面试追问哪种变体（如把5换成任意K、或要求流式处理），都能基于这三块积木快速作答。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode