解
第一步，万年不变的查错。如果给的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的。没有太大的难点。
