LeetCode进阶-1086(Hash Table)

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

概要

本篇主要介绍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 思想

考虑题目描述id限制在1~1000之间,自然可以联想到Hash思想里面比较经典桶结构,考虑使用1~1001的桶结构来存储不同id,数组下标即id。每个id对应一个排序数组存储前5排名的分数,具体实现思路如下:

  1. 1、二维数组int n[1001][5]存储id,排前5名分数数组,分数数组降序排列。

  2. 2、遍历items数组:

  3. i.若n[i]为null说明为新id,创建n[i]=int[5]的排序数组,并将当前分数加入数组第1位;

  4. ii.否则,若score得分低于排序数组中最后一位n[i][4]最小值,则继续循环;

  5. iii.否则,for循环遍历排序数组,交换排序插入新分数;

  6. 3、遍历数组n,若n[i]数组为null,说明当前桶中无数据即无对应学生id,循环继续;

  7. 否则,取出n[i]处排序数组,循环累加总分计算平均分,id和平均分存入数组。

方法二:堆排序

堆实现思路相对简单,使用大小为5的最小堆队列,每次插入新值,移除队头的最小值,保证队列是最大的5个数,这样队列中始终是排名前5的分数。遍历完成后再计算每个id对应堆队列的平均分。为什么使用最小堆是因为Java标准库中的堆队列PriorityQueue的设定就是最小堆(标准库:->_-> 怪我咯),堆实现相对简单因此不作详细思路拆分,直接上代码。

编码实践

Hash实现

  1. public int[][] highFive(int[][] items) {

  2. int n[][] = new int[1001][];

  3. for (int i = 0; i < items.length; ++i) {

  4. int id = items[i][0];

  5. int score = items[i][1];

  6. if (n[id] == null) {

  7. n[id] = new int[5];

  8. n[id][0] = score;

  9. continue;

  10. }

  11. if (score <= n[id][4]) {

  12. continue;

  13. }

  14. for (int j = 0; j < 5; j++) {

  15. if (score > n[id][j]) {

  16. int temp = n[id][j];

  17. n[id][j] = score;

  18. score = temp;

  19. }

  20. }

  21. }

  22. List<int[]> result = new ArrayList<>();

  23. for (int i = 0; i < 1001; ++i) {

  24. if (n[i] == null) {

  25. continue;

  26. }

  27. int total = 0;

  28. for (int score : n[i]) {

  29. total += score;

  30. }

  31. result.add(new int[] { i, total / 5 });

  32. }

  33. return result.toArray(new int[0][0]);

  34. }

LeetCode进阶-1086(Hash Table)

堆实现

  1. public int[][] highFive(int[][] items) {

  2. List<Integer> ids = new ArrayList<Integer>();

  3. HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<Integer, PriorityQueue<Integer>>();

  4. for (int i = 0; i < items.length; ++i) {

  5. PriorityQueue<Integer> queue = map.get(items[i][0]);

  6. if (queue == null) {

  7. queue = new PriorityQueue<Integer>(5);

  8. map.put(items[i][0], queue);

  9. ids.add(items[i][0]);

  10. }

  11. queue.add(items[i][1]);

  12. if (queue.size() > 5) {

  13. queue.poll();

  14. }

  15. }

  16. int result[][] = new int[ids.size()][2];

  17. for (int i = 0; i < ids.size(); ++i) {

  18. PriorityQueue<Integer> queue = map.get(ids.get(i));

  19. int sum = 0;

  20. while (!queue.isEmpty()) {

  21. sum += queue.poll();

  22. }

  23. result[i][0] = ids.get(i);

  24. result[i][1] = sum / 5;

  25. }

  26. return result;

  27. }

LeetCode进阶-1086(Hash Table)

彩蛋

仔细观察上述两种思路的实现代码会发现,有几处for循环的时候使用的都是++i,而不是i++,这便是本篇当中的彩蛋。关于彩蛋后续不定期会有讲解(废话...彩蛋不就是下次才能看明白的么->_->)

LeetCode进阶-1086(Hash Table)

扫一扫 关注我的微信订阅号



原文始发于微信公众号(Aeiric):LeetCode进阶-1086(Hash Table)