0506. Relative Ranks ==================== 题目信息 -------- :题号: 0506 :难度: Easy :主题: 唯一分数、降序排名、奖牌名称、原下标对应 :原题: `LeetCode 0506 `_ :重点: 分数互不相同、最高三名使用固定字符串、其余返回十进制名次、结果保持运动员原顺序 题目重述 -------- 给定整数数组 ``score``,其中 ``score[i]`` 是第 ``i`` 名运动员的得分,所有得分互不相同。按得分从高到低确定名次,并返回与原数组下标一一对应的字符串数组。 第 1、2、3 名分别写为 ``"Gold Medal"``、``"Silver Medal"`` 和 ``"Bronze Medal"``;第 4 名及以后写为对应十进制名次。输出顺序不是排名顺序,而是输入运动员的原顺序。 自建示例 -------- 输入顺序与名次顺序不同: .. code-block:: text 输入:score = [88,92,75,99] 输出:["Bronze Medal","Silver Medal","4","Gold Medal"] 解释:99、92、88、75 分别位列第 1 至第 4 名,再把名次写回各自原下标。 只有一名运动员: .. code-block:: text 输入:score = [42] 输出:["Gold Medal"] 解释:唯一运动员排名第一。 排序下标而不是改写得分 ---------------------- 把 ``(score, originalIndex)`` 按得分降序排列,排序后数组位置 ``rank`` 就是名次 ``rank + 1``。将前三名映射为奖牌文本,其余名次转成十进制字符串并写回原下标,因而不会丢失输入顺序。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector findRelativeRanks( std::vector& score) { std::vector> order; for (int i = 0; i < static_cast(score.size()); ++i) { order.push_back({score[i], i}); } std::sort(order.begin(), order.end(), [](const auto& left, const auto& right) { return left.first > right.first; }); std::vector result(score.size()); const std::string medals[3] = { "Gold Medal", "Silver Medal", "Bronze Medal"}; for (int rank = 0; rank < static_cast(order.size()); ++rank) { int index = order[rank].second; result[index] = rank < 3 ? medals[rank] : std::to_string(rank + 1); } return result; } }; 代码分析 -------- 得分互不相同使排序后的顺序唯一;保存原下标让排名标签回到对应运动员,而不是按排名顺序返回。排序耗时 ``O(n log n)``,结果和排序数组额外占用 ``O(n)`` 空间。