Description:
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.
給出一系列學(xué)生分?jǐn)?shù)熊户，求出每個(gè)學(xué)生最高的5門分?jǐn)?shù)的平均分。
Example:
Given results = [[1,91],[1,92],[2,93],[2,99],[2,98],[2,97],[1,60],[1,58],[2,100],[1,61]]
Return
Link:
http://www.lintcode.com/en/problem/high-five/
解題思路：
本題重點(diǎn)是如果存儲(chǔ)每個(gè)學(xué)生最高的5門的成績(jī)缩膝，這里針對(duì)每個(gè)學(xué)生可以使用一個(gè)vector独撇，這個(gè)vector容積為5屑墨，從第0到第4位以遞減的方式儲(chǔ)存5門成績(jī)躁锁；當(dāng)輸入一個(gè)成績(jī)時(shí)，從第0位開(kāi)始比較卵史，如果輸入的成績(jī)大于這一位置的原有成績(jī)時(shí)战转，數(shù)組由這一位置整體向后挪一位，并且更新這一位置的成績(jī)以躯。
Time Complexity：
O(N)
完整代碼：
map<int, double> highFive(vector<Record>& results) { map<int, vector<double>> record; map<int, double> output; for(Record r : results) { if(record[r.id].size() == 0) { vector<double> temp(5, 0); helper(temp, r.score); record[r.id] = temp; } else { helper(record[r.id], r.score); } } for(auto a : record) { double sum = 0; for(double d : a.second) sum += d; output[a.first] = sum/5; } return output; } void helper(vector<double>& v, int score) { for(int i = 0; i < 5; i++) { if(score <= v[i]) continue; else { for(int j = 4; j > i; j--) v[j] = v[j-1]; v[i] = score; return; } } }
