What is the best approach for Relative Ranks?

The best default approach is to store each score with its original index, sort by score descending, and fill the answer array using medal strings for the top three placements and rank numbers for the rest.

Why does Relative Ranks need original indices?

After sorting, athletes move away from their input positions. You need the original indices so each computed rank label can be written back into the correct slot of the returned array.

Can I solve Relative Ranks with a heap instead of sorting?

Yes. A max-heap lets you repeatedly extract the next highest score and assign the next placement. That matches the problem's heap topic, but sorting is usually shorter and easier when the full array is given upfront.

What is the main Array plus Sorting pattern in this problem?

The pattern is sort transformed array entries while carrying enough metadata to rebuild the original layout. In Relative Ranks, that metadata is the athlete's original index.

Why are unique scores important in Relative Ranks?

Unique scores guarantee a strict ordering, so every athlete gets exactly one placement with no tie logic. That keeps the implementation focused on ranking order and output mapping rather than shared ranks.

#506

Easy

auto_awesome数组·排序

LeetCode 题解工作台

相对名次

给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都互不相同。运动员将根据得分决定名次，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：名次第 1 的运动员获金…

数组排序堆（优先队列）

题目描述

给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。

运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：

名次第 1 的运动员获金牌 "Gold Medal" 。
名次第 2 的运动员获银牌 "Silver Medal" 。
名次第 3 的运动员获铜牌 "Bronze Medal" 。
从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 "x"）。

使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

示例 1：

输入：score = [5,4,3,2,1]
输出：["Gold Medal","Silver Medal","Bronze Medal","4","5"]
解释：名次为 [1^st, 2^nd, 3^rd, 4^th, 5^th] 。

示例 2：

输入：score = [10,3,8,9,4]
输出：["Gold Medal","5","Bronze Medal","Silver Medal","4"]
解释：名次为 [1^st, 5^th, 3^rd, 2^nd, 4^th] 。

提示：

n == score.length
1 <= n <= 10⁴
0 <= score[i] <= 10⁶
score 中的所有值 互不相同

lightbulb

解题思路

方法一：排序

我们使用一个数组 $\textit{idx}$ 存储 $0$ 到 $n-1$ 的下标，然后对 $\textit{idx}$ 进行排序，排序规则为：按照 $\textit{score}$ 的值从大到小排序。

然后我们定义一个数组 $\textit{top3} = [\text{Gold Medal}, \text{Silver Medal}, \text{Bronze Medal}]$ ，遍历 $\textit{idx}$ ，对于每个下标 $j$ ，如果 $j$ 小于 $3$ ，则 $\textit{ans}[j]$ 为 $\textit{top3}[j]$ ，否则为 $j+1$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{score}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        n = len(score)
        idx = list(range(n))
        idx.sort(key=lambda x: -score[x])
        top3 = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        ans = [None] * n
        for i, j in enumerate(idx):
            ans[j] = top3[i] if i < 3 else str(i + 1)
        return ans

speed

复杂度分析

指标	值
时间	O(n + m)
空间	O(m)

psychology

面试官常问的追问

外企场景

question_mark
They want to see whether you preserve original indices after sorting descending scores.
question_mark
They may ask why unique scores remove tie-handling logic from Relative Ranks.
question_mark
They are checking whether you notice the output order is input order, not sorted order.

warning

常见陷阱

外企场景

error
Sorting the scores alone and forgetting which athlete each score belonged to.
error
Writing medal labels in sorted order and returning that sorted array instead of mapping back to original positions.
error
Using zero-based rank strings like "3" for the fourth athlete instead of converting placement to 1-based rank text.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return only numeric ranks without medal strings, which removes the top-three special-case branch.
arrow_right_alt
Handle duplicate scores, which changes Relative Ranks into a tie-ranking problem with shared placements.
arrow_right_alt
Process athletes as they arrive, where a heap becomes more natural than one final sorting pass.

help

常见问题

外企场景

继续练习

#502 IPO #621 任务调度器 #630 课程表 III