Lintcode - High Five

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

Analysis: this is a simple problem.

Take away: how to iterator over a hashmap

HashMap<Integer, PriorityQueue<Double>> idScores= new HashMap<Integer, PriorityQueue<Double>>();
Iterator it = idScores.entrySet().iterator();

while(it.hasNext()){
    Map.Entry<Integer, PriorityQueue<Double>> pair = (Map.Entry) it.next();
    //pair.getKey()
    //pair.getValue()
}

Solution

public Map<Integer, Double> highFive(Record[] results) {
    Map<Integer, Double> result = new HashMap<Integer, Double>();
    HashMap<Integer, PriorityQueue<Double>> idScores = new HashMap<Integer, PriorityQueue<Double>>();

    for (int i = 0; i < results.length; i++){ 
        int id = results[i].id;
        double score = results[i].score;
        PriorityQueue<Double> queue = idScores.get(id);
        if (queue == null){
            queue = new PriorityQueue<Double>();
            queue.offer(score);
            idScores.put(id, queue);
        } else {
            queue.offer(score);
            while (queue.size() > 5){
                queue.poll();
            }
        }
    }


    Iterator it = idScores.entrySet().iterator();
    while (it.hasNext()){
        Map.Entry<Integer, PriorityQueue<Double>> pair = (Map.Entry)it.next();
        double totalScore = 0;
        PriorityQueue<Double> scores = pair.getValue();
        while (!scores.isEmpty()){
            totalScore += scores.poll();
        }
        result.put(pair.getKey(), totalScore/5);
    }

    return result;   
}