LintCode - 613 High Five

https://xuezhashuati.blogspot.com/2017/03/lintcode-613-high-five.html
There are two properties in the node student id and scores, 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
思路
根据题意，对于每一个id，我们维护一个大小为K的min-heap。一个一个把Record放进去，如果容量超了，就把最小的踢掉。这样heap里永远是最大的K个。
全部放完以后，对于每一个id，我们把heap里的Record拿出来算一下平均数。

    public Map<Integer, Double> highFive(Record[] results) {
        // Write your code here
        
        Map<Integer, Double> result = new HashMap<Integer, Double>();
        HashMap<Integer, PriorityQueue<Record>> map = new HashMap<Integer, PriorityQueue<Record>>();
        
        int k = 5;
        for (Record r : results) {
            if (!map.containsKey(r.id)) {
                PriorityQueue<Record> pq = new PriorityQueue<Record>(k, new Comparator<Record>() {
                   public int compare(Record a, Record b) {
                       return a.score - b.score; // min-heap
                   } 
                });
                map.put(r.id, pq);
            }
            
            map.get(r.id).add(r);
            if (map.get(r.id).size() > k) {
                map.get(r.id).poll();
            }
        }
        
        for (Map.Entry<Integer, PriorityQueue<Record>> entry : map.entrySet()) {
            int id = entry.getKey();
            PriorityQueue<Record> pq = entry.getValue();
            double average = 0;
            int num = pq.size();
            while (!pq.isEmpty()) {
                average += pq.poll().score;
            }
            average /= num;
            result.put(id, average);
        }
        
        return result;
    }

http://www.cnblogs.com/aprilyang/p/6702149.html

看了下答案，hashmap里面value用arraylist，可能会快一点点，这个要根据数据集来看决定采用哪种结构。因为用arraylist的话，每次都是O(n)时间来查找最小值来替换，用heap的话是O(log(n))，在前五个添加的时候慢一点，但是后面替换快很多。

    public Map<Integer, Double> highFive(Record[] results) {
        Map<Integer, Double> answer = new HashMap<Integer, Double>();
        Map<Integer, List<Integer>> hash = new HashMap<Integer, List<Integer>>();

        for (Record r : results) {
            if (!hash.containsKey(r.id)){
                hash.put(r.id, new ArrayList<Integer>());
            }

            if (hash.get(r.id).size() < 5) {
                hash.get(r.id).add(r.score);
            } else {
                int index = 0;
                for (int i = 1; i < 5; ++i)
                    if (hash.get(r.id).get(i) < hash.get(r.id).get(index))
                        index = i;
                if (hash.get(r.id).get(index) < r.score)
                    hash.get(r.id).set(index, r.score);
            }
        }

        for (Map.Entry<Integer, List<Integer>> entry : hash.entrySet()) {
            int id = entry.getKey();
            List<Integer> scores = entry.getValue();
            double average = 0;
            for (int i = 0; i < 5; ++i)
                average += scores.get(i);
            average /= 5.0;
            answer.put(id, average);
        }
        return answer;
    }