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

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.

• 相关文章
• 全局相关文章