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".
Example 1:
Input: [5, 4, 3, 2, 1] Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"] Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". For the left two athletes, you just need to output their relative ranks according to their scores.Note:
N is a positive integer and won't exceed 10,000.All the scores of athletes are guaranteed to be unique.思路：关键在于如何在排序的同时，记录下原始的索引和排序后的位置。所以利用map，map自动进行排序，pair记录下元素及其原始位置。map中pair顺序即排序之后的顺序。
代码1：
class Solution { public: vector<string> findRelativeRanks(vector<int>& nums) { map<int, int> mp; for (int i = 0; i < nums.size(); i++) mp[nums[i]] = i; vector<string> ans(mp.size(), ""); int cnt = 1; for (map<int, int>::reverse_iterator it = mp.rbegin(); it != mp.rend(); it++, cnt++) { if (cnt == 1) ans[it->second] = "Gold Medal"; else if (cnt == 2) ans[it->second] = "Silver Medal"; else if (cnt == 3) ans[it->second] = "Bronze Medal"; else ans[it->second] = to_string(cnt); } return ans; } };代码2：
class Solution { public: vector<string> findRelativeRanks(vector<int>& nums) { vector <pair <int, int> > scoreIdx; for (int i = 0; i < nums.size(); ++i) { scoreIdx.emplace_back(nums[i], i); } sort(scoreIdx.begin(), scoreIdx.end()); reverse(scoreIdx.begin(), scoreIdx.end()); vector <string> ans (nums.size()); for (int i = 0; i < nums.size(); ++i) { if (i==0) ans[scoreIdx[i].second] = "Gold Medal"; else if (i==1) ans[scoreIdx[i].second] = "Silver Medal"; else if (i==2) ans[scoreIdx[i].second] = "Bronze Medal"; else ans[scoreIdx[i].second] = to_string(i+1); } return ans; } };代码3：
class Solution { public: vector<string> findRelativeRanks(vector<int>& nums) { vector <pair <int, int> > scoreIdx; for (int i = 0; i < nums.size(); ++i) { scoreIdx.emplace_back(nums[i], i); } sort(scoreIdx.begin(), scoreIdx.end()); reverse(scoreIdx.begin(), scoreIdx.end()); vector <string> ans (nums.size()); for (int i = 0; i < nums.size(); ++i) { if (i==0) ans[scoreIdx[i].second] = "Gold Medal"; else if (i==1) ans[scoreIdx[i].second] = "Silver Medal"; else if (i==2) ans[scoreIdx[i].second] = "Bronze Medal"; else ans[scoreIdx[i].second] = to_string(i+1); } return ans; } };