506. Relative Ranks 相对排名

题目描述

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