613.High Five

1.Description(Medium)

There are two properties in the node studentidandscores, to ensure that each student will have at least 5 points, find the average of 5 highest scores for each person.

Example

Given results = [[1,91],[1,92],[2,93],[2,99],[2,98],[2,97],[1,60],[1,58],[2,100],[1,61]]

Return

2.Code

根据题意，对于每一个id，我们维护一个大小为K的min-heap。(HashMap(id,heap)实现)

一个一个把Record放进去，如果容量超了，就把最小的踢掉。这样heap里永远是最大的K个。全部放完以后，对于每一个id，我们把heap里的Record拿出来算一下平均数。

注意a/b只有a 和 b都是double的时候结果才是double.

求最大的K个值==>维护minheap ==> return a-b;

求最小的K个值 ==>维护maxheap ==> return b-a;

public Map<Integer, Double> highFive(Record[] results) {

        Map<Integer,Double> highfive=new HashMap<Integer,Double>();
        HashMap<Integer,PriorityQueue<Record>> queue=new HashMap<>();
        //建立每个id的minheap
        for(int i=0;i<results.length;i++){
            int ids=results[i].id;
            int scores=results[i].score;
            if(queue.containsKey(ids)){
                if(queue.get(ids).size()<5){
                    queue.get(ids).offer(results[i]);
                }else{
                    if(queue.get(ids).peek().score<scores){
                        queue.get(ids).poll();
                        queue.get(ids).offer(results[i]);                       
                    }
                }
            }else{
                //在这里定义每个priorityqueue的排序方法
                PriorityQueue<Record> minheap=new PriorityQueue<Record>(5,new Comparator<Record>(){
                    @Override
                    public int compare(Record a,Record b){
                        return a.score-b.score;
                    }
                });
                minheap.offer(results[i]);
                queue.put(ids,minheap);
            }
        }

        //遍历得到结果
        for(Map.Entry<Integer, PriorityQueue<Record>> entry: queue.entrySet()){
            int ids=entry.getKey();
            PriorityQueue<Record> heap=entry.getValue();
            double sum=0;
            int size=heap.size();
            while(!heap.isEmpty()){
                sum=sum+heap.poll().score;
            }
            double avg=sum/(double)size;

            highfive.put(ids, avg);
        }

        return highfive;
    }