Leetcode - High Five
https://leetcode.com/problems/high-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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | func highFive(items [][]int) [][]int { if len(items) == 0 { return [][]int{} } hash := map[int][]int{} for _, item := range items { hash[item[0]] = append(hash[item[0]], item[1]) } result := [][]int{} for key, val := range hash { sort.Slice(val, func(i, j int) bool { return val[i] > val[j] }) sum := 0 count := min(len(val), 5) i := 0 for i < count { sum += val[i] i++ } result = append(result, []int{key, sum/count}) } sort.Slice(result, func(i, j int) bool { return result[i][0] < result[j][0] }) return result}func min(a, b int) int{ if a < b { return a } return b} |
It's unbelievably simpler. Currently I'm using sort and beating 100%.
But I think it would be better to use a heap for every student and try to avoid sort. Init a heap only uses O(n) and pop elements also uses O(n). But that would be more complicated for just an easy issue.
评论 (0)
