High Five解题报告

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.
给出一系列学生分数,求出每个学生最高的5门分数的平均分。

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/

解题思路:

本题重点是如果存储每个学生最高的5门的成绩,这里针对每个学生可以使用一个vector,这个vector容积为5,从第0到第4位以递减的方式储存5门成绩;当输入一个成绩时,从第0位开始比较,如果输入的成绩大于这一位置的原有成绩时,数组由这一位置整体向后挪一位,并且更新这一位置的成绩。

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; } } }

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 江小鱼是个地地道道的农村姑娘,出生在一个普普通通的农民家庭,父亲是这个家里的第七个孩子,祖父和祖母养育了五...
    秾华如梦ing阅读 422评论 0 4
  • 陈伟霆平时多数住在近郊的排屋里,偶尔才会回老宅,今天正好赶上家中有事。这会儿他正洗完澡看书,听到客厅里仲伯能大呼小...
    焦者阅读 449评论 0 0