Имея список оценок разных учащихся, items, где items[i] = [IDi, scorei] представляет одну оценку учащегося с IDi, рассчитайте среднее значение пятерки лучших для каждого учащегося.
Возвратите ответ в виде массива парresult, гдеresult[j] = [IDj, topFiveAveragej]представляет учащегося сIDjи его пять лучших средних. СортироватьresultпоIDjв возрастающем порядке.
Среднее значение пятерки лучших учащегося рассчитывается путем деления суммы пяти лучших оценок учащегося на 5 с помощью целочисленного деления.
Подход:
Учитывая, что нам нужно выбрать 5 лучших значений каждого идентификатора, нам нужен способ узнать, чтобы хранить только самые большие 5 или менее значений для каждого идентификатора. Используя минимальную кучу, мы можем определить, какие значения являются 5 самыми большими значениями.
Таким образом, для каждого идентификатора мы можем сопоставить минимальную кучу с максимальным размером 5, и всякий раз, когда куча заполнена, и если входящее значение больше, чем значение заголовка, мы можем вытолкнуть голову и добавить входящее значение, чтобы сохранить текущие верхние 5 самые большие значения в очереди. В любое время min-heap будет иметь 5 самых больших значений, наблюдаемых до сих пор для каждого идентификатора.
После того, как мы вставили все входные пары, мы можем просмотреть каждый идентификатор и найти среднее значение всех элементов в минимальной куче.
Учитывая ограничения, на входе может быть 1000 элементов, мы можем достичь наихудшего случая O (n) — n — количество входных данных, поэтому максимум 1000. Вставка и удаление в минимальной куче будет log (n).
public int[][] highFive(int[][] items)
{
Map‹Integer,PriorityQueue‹Integer›› map = new HashMap();
for(int i=0;i‹items.length;i++)
{
PriorityQueue‹Integer› p = map.get(items[i][0]);
если (р == ноль)
{
p=новая очередь PriorityQueue‹Integer›(5);
map.put(элементы[i][0],p);
}
если ( p.size()‹5 )
{
p.add (элементы [i] [1]);
}
еще{
если(p.peek().intValue() ‹ элементы[i][1])
{
п.опрос();
p.add (элементы [i] [1]);
}
}
map.put(элементы[i][0],p);
}
List‹int[]› res = new LinkedList();
for(Map.Entry‹Integer,PriorityQueue‹Integer›› запись: map.entrySet()){
PriorityQueue‹Integer› pq = entry.getValue();
целая сумма=0;
пока(!pq.isEmpty()){
сумма+=pq.poll();
}
сумма=сумма/5;
res.add(new int[]{entry.getKey(),sum});
}
вернуть res.toArray (новый интервал [0] [0]);
}
