题目描述
Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".
示例
输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
说明: 前两名运动员获得了最高的三个分数，因此他们获得了'金牌'、'银牌'和'铜牌'。对于剩下的两名运动员，只需根据他们的分数输出相对排名即可。
思路
对于给定的得分情况，找出前三名并给予相应的称号，其余以数字作为其名称。利用优先队列进行记录每个元素的位置和元素值，优先队列的特点是 top 始终是所有元素中最大的那个。
第二种方法，可以用 map 来解决，将 nums 中的元素值作为 map 的 key 从而实现将 nums 排序，同时保存 nums 的 index 到 map 中。
代码实现
方法一：优先队列
class Solution {
public:
vector<string> findRelativeRanks(vector<int>& nums) {
vector<string> res(nums.size());
priority_queue<pair<int, int>> temp;
for (size_t i = 0, len = nums.size(); i < len; ++i) {
temp.push({nums[i], i});
}
int count = 1;
while (temp.size()) {
auto elem = temp.top();
temp.pop();
if (count == 1) res[elem.second] = "Gold Medal";
else if (count == 2) res[elem.second] = "Silver Medal";
else if (count == 3) res[elem.second] = "Bronze Medal";
else res[elem.second] = to_string(count);
++count;
}
return res;
}
};
方法二：有序映射
class Solution {
public:
vector<string> findRelativeRanks(vector<int>& nums) {
vector<string> res(nums.size());
map<int, int> ma;
for (int i = 0; i != nums.size(); ++i) {
ma[nums[i]] = i;
}
int count = 1;
for (map<int, int>::reverse_iterator it = ma.rbegin(); it != ma.rend(); ++it, ++count) {
if (count == 1) res[it->second] = "Gold Medal";
else if (count == 2) res[it->second] = "Silver Medal";
else if (count == 3) res[it->second] = "Bronze Medal";
else res[it->second] = to_string(count);
}
return res;
}
};