LintCode 613. 优秀成绩

原题

解

第一步，万年不变的查错。如果给的array是null或空，直接return 0

    public Map<Integer, Double> highFive(Record[] records) {
        Map<Integer, Double> results = new HashMap<>();
        if(records == null || records.length == 0) {
            return results;
        }
        ...
    }

这个题其实就是考PriorityQueue。实际问题简化后就是给你一堆数字，找到前五个。PriorityQueue的默认排序是从小到大，所以正好用来做这个。只留5个数字，超过5个后，每次需要加入新的，就必须要与5个数字里面最小的对比。这样就可以保证，这个queue里面的5个数就是最大的5个数。有了这个思路，剩下的就简单了，先遍历一遍array，把每个id对应的score的最高的5个用PriorityQueue的方式选出来。

        Map<Integer, Queue<Integer>> map = new HashMap<>();
        
        for (Record record : records) {
            Queue<Integer> pq = map.getOrDefault(record.id, new PriorityQueue<>());
            if (pq.size() < 5) {
                pq.add(record.score);
            } else if (record.score > pq.peek()) {
                pq.poll();
                pq.add(record.score);
            }
            map.put(record.id, pq);
        }

然后就是去平均数了。从map里面把每个queue取平均数。放到results里面，return了就完成了。

        for (Map.Entry<Integer, Queue<Integer>> entry : map.entrySet()) {
            Queue<Integer> scores = entry.getValue();
            int size = scores.size();
            int totalScore = 0;
            while (!scores.isEmpty()) {
                totalScore += scores.poll();
            }
            results.put(entry.getKey(), totalScore / (double) size);
        }
        
        return results;

完整的code

/**
 * Definition for a Record
 * class Record {
 *     public int id, score;
 *     public Record(int id, int score){
 *         this.id = id;
 *         this.score = score;
 *     }
 * }
 */
public class Solution {
    /**
     * @param records a list of <student_id, score>
     * @return find the average of 5 highest scores for each person
     * Map<Integer, Double> (student_id, average_score)
     */
    public Map<Integer, Double> highFive(Record[] records) {
        Map<Integer, Double> results = new HashMap<>();
        if (records == null || records.length == 0) {
            return results;
        } 
        
        Map<Integer, Queue<Integer>> map = new HashMap<>();
        
        for (Record record : records) {
            Queue<Integer> pq = map.getOrDefault(record.id, new PriorityQueue<>());
            if (pq.size() < 5) {
                pq.add(record.score);
            } else if (record.score > pq.peek()) {
                pq.poll();
                pq.add(record.score);
            }
            map.put(record.id, pq);
        }
        
        for (Map.Entry<Integer, Queue<Integer>> entry : map.entrySet()) {
            Queue<Integer> scores = entry.getValue();
            int size = scores.size();
            int totalScore = 0;
            while (!scores.isEmpty()) {
                totalScore += scores.poll();
            }
            results.put(entry.getKey(), totalScore / (double) size);
        }
        
        return results;
        
    }
}

分析

时间复杂度

遍历需要O(n)，插入到priorityQueue需要O(n)，提取因为只要前5个，所以是nlog5，所以总共就是O(n)。

空间复杂度

建立了2个map，每个size都是id的个数，所以是O(m)，m是id的个数。

这个题关键在找前五，所以就是考用PriorityQueue的。没有太大的难点。