Higest 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.

Example
Given results = [[1,91],[1,92],[2,93],[2,99],[2,98],[2,97],[1,60],[1,58],[2,100],[1,61]]

Return:

Analyze

根据题意,对于每一个id,我们维护一个大小为K的min-heap。一个一个把Record放进去,如果容量超了,就把最小的踢掉。这样heap里永远是最大的K个。
全部放完以后,对于每一个id,我们把heap里的Record拿出来算一下平均数。(用 unordered_map<int, priority_queue<double>> 储存数据,其中的min heap优先队列保持size为5,然后对各自的top 5求平均值)

Solution

/**
 * Definition for a Record
 * class Record {
 * public:
 *   int id, score;
 *   Record(int id, int score) {
 *     this->id = id;
 *     this->score = score;
 *   }
 * };
 */
class Solution {
 public:
  map<int, double> highFive(vector<Record>& results) {
    int len = results.size();

    map<int, priority_queue<int, vector<int>, greater<int>>> mp;  // id, min-heap
    map<int, double> result;
    // Save all the points for each student
    for (int i = 0; i < len; ++i) {
      int studentId = results[i].id;
      int studentScore = results[i].score;
      mp[studentId].push(studentScore);
      if (mp[studentId].size() > 5) mp[studentId].pop();
    }

    // 分别处理每一个学生的成绩
    for (auto m : mp) {
      double sum = 0;
      while (m.second.size() > 0) {
        sum += m.second.top();
        m.second.pop();
      }
      result[m.first] = sum / 5;  // strictly speacking, it needs to check if the student has >= 5 courses
    }
    return result;
  }
};
]
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""