506. Relative Ranks

▶ 给出一个数组，要求给出每个元素在排序以后的下标，并且给前三名金银铜牌。如输入 [ 4, 5, 1, 3, 0 ]，则输出 [ 2, 1, 4, 3, 5 ]，（得 5 分的第一名，的 4 分的第二名，以此类推）。题目本身比较简单，但是思想比较重要。

● 代码，10 ms，使用数对记录下标，类似第 1 题中构造的那个结构，用其中一个数值来排序，另一个值记录了该值在原数组中的下标，用于将名次放回正确的位置上。

 1 class Solution
 2 {
 3 public:
 4     vector<string> findRelativeRanks(vector<int>& nums)
 5     {
 6         vector <pair <int, int> > scoreIdx;
 7         vector <string> ans(nums.size());
 8         int i;
 9         for (i = 0; i < nums.size(); ++i)
10             scoreIdx.emplace_back(nums[i], i);
11 
12         sort(scoreIdx.begin(), scoreIdx.end());
13         reverse(scoreIdx.begin(), scoreIdx.end());
14 
15         for (i = 0; i < nums.size(); ++i)
16         {
17             if (i == 0)
18                 ans[scoreIdx[i].second] = "Gold Medal";
19             else if (i == 1)
20                 ans[scoreIdx[i].second] = "Silver Medal";
21             else if (i == 2)
22                 ans[scoreIdx[i].second] = "Bronze Medal";
23             else
24                 ans[scoreIdx[i].second] = to_string(i + 1);
25         }
26         return ans;
27     }
28 };

● 伴随排序，利用原数组的数值比较，对数组 rank = [ 1, 2, 3, ... , nums.size() ] 进行排序，排序后 rank[ i ] == j 表示 nums 中排第 i 的元素在原 nums 的第 j 个位置上。如下图的例子中，排序后 rank[ 0 ] == 4 表示 nums 中排第 0 的元素在原 nums 的第 4 个位置上，rank[ 2 ] == 3 表示 nums 中排第 2 的元素在原 nums 的第 3 个位置上。

● 代码，13 ms，在本题中，使用降序排序，且 rank 从 1 开始。

 1 class Solution
 2 {
 3 public:
 4     vector<string> findRelativeRanks(vector<int>& nums)
 5     {
 6         vector<int> rank(nums.size()); 
 7         vector<string> output(nums.size());
 8         int i;
 9         for (i = 0; i < nums.size(); rank[i] = i, i++);
10         sort(rank.begin(), rank.end(), [&](int a, int b) {return nums[a] > nums[b]; });// 注意利用 nums 来对 rank 排序
11         for (i = 3; i < nums.size(); i++)
12             output[rank[i]] = to_string(i + 1);
13         if (nums.size() > 0)
14             output[rank[0]] = "Gold Medal";
15         if (nums.size() > 1)
16             output[rank[1]] = "Silver Medal";
17         if (nums.size() > 2)
18             output[rank[2]] = "Bronze Medal";
19 
20         return output;
21     }
22 };