LeetCode进阶-1086
概要
本篇主要介绍LeetCode上第1086题，本篇素材主要来源于日常刷题习惯整理记录，作为数据结构算法开篇，希望更多的展现刷题思路，学习数据结构与算法的方法技巧。本篇会有个小“彩蛋”，“彩蛋”在笔者这里的定义是可以提高算法执行效率的小技巧，后续关于数据结构与算法的系列推文中，笔者也会尽可能多的埋一些“彩蛋”。千里之行，始于足下，共勉～
题意分析
1086 Hign Five
Given a list of scores of different students, return the average score of each student's top five scores in the order of each student's id.
Each entry items[i] has items[i][0] the student's id, and items[i][1] the student's score. The average score is calculated using integer division.
Example 1:
Input: [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
Output: [[1,87],[2,88]]
Explanation:
The average of the student with id = 1 is 87.
The average of the student with id = 2 is 88.6. But with integer division their average converts to 88.
Note:
1 <= items.length <= 1000
items[i].length == 2
The IDs of the students is between 1 to 1000
The score of the students is between 1 to 100
For each student, there are at least 5 scores
翻译版
给出一个不同学生的分数二维数组，根据每个学生的id，将每个学生的排在前五的平均分数返回。
items[i]中items[i][0]代表学生的id，items[i][1]代表学生的得分。平均分数是用整数除法计算
例1：
输入:[1,91]，[1,92]，[2,93]，[2,97]，[1,60]，[2,77]，[1,65]，[1,87]，[1,87][1100],[2100],[2,76]]
输出：[[1,87]，[2,88]]
解释：
id为1的学生的平均数是87。
在id=2的学生中，平均为88.6。但是随着整除，平均值变为88。
备注：
1 <= items.length <= 1000
Items[i].length == 2
学生的id在1到1000之间
这些学生的分数在1到100之间
每个学生至少有5个得分
- 本题在LeetCode上在Hash Table分类下
分析
结合LeetCode的官方分类可以猜测出本题解题思路偏向Hash思想，故至少有一种思路是Hash方向，具体实践时可以尝试不同的解题思路。由于是从很多分数中选出分数最高的前5个计算平均分，因此自然能联想到最大堆的基本数据结构，而Java标准库提供了堆相关的优先队列PriorityQueue，因此第二种思路考虑使用堆思想。
思路设计
方法一：Hash 思想
考虑题目描述种分数值限制在1～100之间，并且可能有多个相同的分数，自然可以联想到Hash思想里面比较经典桶结构，故考虑使用1～100的桶结构来存储不同分数值出现的次数。统计完成后再从100分递减依次从最高分往最低分统计出有效分数的次数，直到次数为5结束，这样可以统计出排名前5的分数。具体实现思路如下：
1、int n[1000][100]存储id,桶数组结构，List<Integer>记录ids，
2、遍历数组：
i.新id=i创建n[i]=int[100]的桶数组，id存入ids，数组存储count
ii.旧id=i在n[score]处自增n[score]=n[score]+1；
3、遍历List<Integer>，根据拿到id从n[1000][100]数组中获取n[id]数组即得到记录次数的桶数组
4、新建初始count=0，total,循环遍历桶数组从数组下标100递减
i.若累加后当前count>=5 根据累加前total和当前count计算最后total当前循环结束
ii.否则，count累加total累加，循环继续
方法二：堆
堆实现思路相对简单，使用大小为5的最小堆队列，每次插入新值，移除队头的最小值，保证队列是最大的5个数，这样队列中始终是排名前5的分数。遍历完成后再计算每个id对应堆队列的平均分。为什么使用最小堆是因为Java标准库中的堆队列PriorityQueue的设定就是最小堆（标准库：->_-> 怪我咯)，堆实现相对简单因此不作详细思路拆分，直接上代码。
编码实践
Hash实现与LeetCode判定
public int[][] highFive(int[][] items) {
int length = items.length;
List<Integer> ids = new ArrayList<>();
int n[][] = new int[1001][101];
for (int i = 0; i < items.length; ++i) {
int id = items[i][0];
int score = items[i][1];
if (!ids.contains(id)) {
n[id] = new int[101];
ids.add(id);
}
n[id][score]++;
}
int result[][] = new int[ids.size()][2];
for (int i = 0; i < ids.size(); ++i) {
int id = ids.get(i);
int count = 0, total = 0;
for (int j = 100; j >= 0; --j) {
if (count + n[id][j] >= 5) {
total = total + (5 - count) * j;
result[i][0] = id;
result[i][1] = total / 5;
break;
} else {
count += n[id][j];
total = total + j * n[id][j];
}
}
}
return result;
}
hash-提交结果
堆实现与LeetCode判定
public int[][] highFive(int[][] items) {
List<Integer> ids = new ArrayList<Integer>();
HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<Integer, PriorityQueue<Integer>>();
for (int i = 0; i < items.length; ++i) {
PriorityQueue<Integer> queue = map.get(items[i][0]);
if (queue == null) {
queue = new PriorityQueue<Integer>(5);
map.put(items[i][0], queue);
ids.add(items[i][0]);
}
queue.add(items[i][1]);
if (queue.size() > 5) {
queue.poll();
}
}
int result[][] = new int[ids.size()][2];
for (int i = 0; i < ids.size(); ++i) {
PriorityQueue<Integer> queue = map.get(ids.get(i));
int sum = 0;
while (!queue.isEmpty()) {
sum += queue.poll();
}
result[i][0] = ids.get(i);
result[i][1] = sum / 5;
}
return result;
}
堆-提交结果
彩蛋
仔细观察上述两种思路的实现代码会发现，有几处for循环的时候使用的都是++i，而不是i++,这便是本篇当中的彩蛋（算法大神自行忽略-）。关于彩蛋后续推文会有讲解（废话...彩蛋不就是下次才能看明白的么->_->)
扫一扫 关注我的微信订阅号
