LC.506 ｜ 相对名次 ｜ 排序 ｜ 排序后映射回原下标（分数唯一）

输入：整数数组score，score[i]表示第i位运动员得分，且所有分数互不相同。

要求：按分数从高到低排名：

• 第 1 名：“Gold Medal”
• 第 2 名：“Silver Medal”
• 第 3 名：“Bronze Medal”
• 第 4…n 名：名次数字字符串（“4”…“n”）

输出：字符串数组answer，其中answer[i]是第i位运动员的名次描述。

---

思路：

这题的核心就是一句话：

排序拿到“名次”，再把名次映射回原来的位置。

做法分两步：

1. 排序得到名次顺序

   • 复制一份sorted = score
   • 按降序排序，sorted[0]就是第一名分数，sorted[1]第二名……

2. 建立“分数 -> 名次字符串”的映射

   • 因为题目保证分数都不重复，所以可以直接用unordered_map<int, string>。
   • 遍历sorted：
     • i=0/1/2 写入三种 Medal
     • i>=3 写入to_string(i+1)（名次从 1 开始）

3. 按原数组顺序填答案

   • ans[i] = mp[score[i]]，就能恢复到原下标对应的名次。

你额外做了reserve + max_load_factor，能减少 rehash，算是工程细节加分。

---

复杂度：

• 时间复杂度：O(N log N)
  • 排序主导。
• 空间复杂度：O(N)
  • sorted+unordered_map+ans。

---

classSolution{public:vector<string>findRelativeRanks(vector<int>&score){intn=(int)score.size();vector<int>sorted=score;sort(sorted.begin(),sorted.end(),greater<int>());unordered_map<int,string>mp;mp.reserve(n*2);mp.max_load_factor(0.7f);for(inti=0;i<n;i++){if(i==0)mp[sorted[i]]="Gold Medal";elseif(i==1)mp[sorted[i]]="Silver Medal";elseif(i==2)mp[sorted[i]]="Bronze Medal";elsemp[sorted[i]]=to_string(i+1);}vector<string>ans(n);for(inti=0;i<n;i++){ans[i]=mp[score[i]];}returnans;}};