Easy

题目描述

给你一个长度为 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"]
解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。

示例 2：

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

提示：

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

解题思路

这道题的核心是根据分数排名并为每个运动员分配相应的名次。

解题思路：

  1. 排序 + 哈希映射法（推荐）：首先创建一个包含分数和索引的数组，然后按分数降序排序。排序后，我们就能知道每个分数对应的名次。使用哈希表记录每个分数对应的名次字符串，最后遍历原数组构建结果。

  2. 堆排序法：使用优先队列（最大堆）来获取排序后的分数，然后建立分数到名次的映射关系。

  3. 直接排序法：对原数组排序后建立映射，但需要额外空间存储原始索引。

具体实现步骤：

  • 创建分数和索引的配对数组
  • 按分数降序排序
  • 遍历排序后的数组，为前三名分配奖牌，其余分配数字名次
  • 使用哈希表存储分数到名次的映射
  • 根据原数组顺序构建最终结果

时间复杂度主要来自排序操作，空间复杂度来自存储映射关系的哈希表。

代码实现

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int n = score.size();
        vector<pair<int, int>> scoreIndex;
        
        // 创建分数和索引的配对
        for (int i = 0; i < n; i++) {
            scoreIndex.push_back({score[i], i});
        }
        
        // 按分数降序排序
        sort(scoreIndex.begin(), scoreIndex.end(), greater<pair<int, int>>());
        
        vector<string> result(n);
        vector<string> medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        
        // 分配名次
        for (int i = 0; i < n; i++) {
            int idx = scoreIndex[i].second;
            if (i < 3) {
                result[idx] = medals[i];
            } else {
                result[idx] = to_string(i + 1);
            }
        }
        
        return result;
    }
};

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        n = len(score)
        
        # 创建分数和索引的配对，按分数降序排序
        score_index = sorted(enumerate(score), key=lambda x: x[1], reverse=True)
        
        result = [''] * n
        medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        
        # 分配名次
        for rank, (idx, _) in enumerate(score_index):
            if rank < 3:
                result[idx] = medals[rank]
            else:
                result[idx] = str(rank + 1)
        
        return result

public class Solution {
    public string[] FindRelativeRanks(int[] score) {
        int n = score.Length;
        var scoreIndex = new List<(int score, int index)>();
        
        // 创建分数和索引的配对
        for (int i = 0; i < n; i++) {
            scoreIndex.Add((score[i], i));
        }
        
        // 按分数降序排序
        scoreIndex.Sort((a, b) => b.score.CompareTo(a.score));
        
        string[] result = new string[n];
        string[] medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        
        // 分配名次
        for (int i = 0; i < n; i++) {
            int idx = scoreIndex[i].index;
            if (i < 3) {
                result[idx] = medals[i];
            } else {
                result[idx] = (i + 1).ToString();
            }
        }
        
        return result;
    }
}

var findRelativeRanks = function(score) {
    const n = score.length;
    
    // 创建分数和索引的配对数组
    const scoreIndex = score.map((s, i) => [s, i]);
    
    // 按分数降序排序
    scoreIndex.sort((a, b) => b[0] - a[0]);
    
    const result = new Array(n);
    const medals = ["Gold Medal", "Silver Medal", "Bronze Medal"];
    
    // 分配名次
    for (let i = 0; i < n; i++) {
        const idx = scoreIndex[i][1];
        if (i < 3) {
            result[idx] = medals[i];
        } else {
            result[idx] = (i + 1).toString();
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要来自排序操作
空间复杂度O(n)需要额外数组存储分数索引配对和结果数组