前五科的均分

1086. 前五科的均分

给你一个不同学生的分数列表 items，其中 items[i] = [ID_i, score_i] 表示 ID_i 的学生的一科分数，你需要计算每个学生 最高的五科 成绩的 平均分。

返回答案 result 以数对数组形式给出，其中 result[j] = [ID_j, topFiveAverage_j] 表示 ID_j 的学生和他 最高的五科 成绩的 平均分。result 需要按 ID_j 递增的 顺序排列 。

学生 最高的五科 成绩的 平均分 的计算方法是将最高的五科分数相加，然后用 整数除法 除以 5 。

示例 1：

输入：items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
输出：[[1,87],[2,88]]
解释：
ID = 1 的学生分数为 91、92、60、65、87 和 100 。前五科的平均分 (100 + 92 + 91 + 87 + 65) / 5 = 87
ID = 2 的学生分数为 93、97、77、100 和 76 。前五科的平均分 (100 + 97 + 93 + 77 + 76) / 5 = 88.6，但是由于使用整数除法，结果转换为 88

示例 2：

输入：items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
输出：[[1,100],[7,100]]

提示：

1 <= items.length <= 1000
items[i].length == 2
1 <= ID_i <= 1000
0 <= score_i <= 100
对于每个 ID_i，至少存在五个分数

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<vector<int>> highFive(vector<vector<int>>& items) { } };

java 解法, 执行用时: 4 ms, 内存消耗: 42.9 MB, 提交时间: 2023-10-15 17:41:34

class Solution {
    public int[][] highFive(int[][] items) {

        Arrays.sort(items, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
        
        //修改点一：利用 set 计算结果的长度，避免 id 不连续造成的错误
        HashSet<Integer> set = new HashSet<>();
        for(int[] item : items){
            set.add(item[0]);
        }

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

        //修改点二：使用 index 来标识结果位置
        int index = 0;
        for (int i = 0; i < items.length; i++) {
            if (i == 0 || items[i][0] != items[i - 1][0]) {
                result[index][0] = items[i][0];
                for (int j = i; j < i + 5; j++) {
                    result[index][1] += items[j][1];
                }
                result[index][1] /= 5;  
                i += 4; 
                index++;
            }
        }
        return result;
    }
}

golang 解法, 执行用时: 8 ms, 内存消耗: 4.1 MB, 提交时间: 2023-10-15 17:40:22

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

func highFive(items [][]int) [][]int {
	val := make(map[int]*IntHeap)
	for i := 0; i < len(items); i++ {
		if _, ok := val[items[i][0]]; !ok {
			h := &IntHeap{}
			heap.Init(h)
			val[items[i][0]] = h
		}
		heap.Push(val[items[i][0]], items[i][1])
		if val[items[i][0]].Len() > 5 {
			heap.Pop(val[items[i][0]])
		}
	}
	ret := make([][]int, 0)
	for k, h := range val {
		score := 0
		for h.Len() > 0 {
			score += heap.Pop(h).(int)
		}
		ret = append(ret, []int{k, score / 5})
	}
	sort.Slice(ret, func(i, j int) bool {
		return ret[i][0] < ret[j][0]
	})
	return ret
}

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-15 17:39:48

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        items.sort(key=lambda item:[-item[0], item[1]],reverse=True)
        res = defaultdict(list)
        for item in items:
            student_id, score = item
            if len(res[student_id]) < 5:
                res[student_id].append(score)
        return sorted([[student_id, sum(score) // 5] for student_id, score in res.items()])

上一题

下一题

详情