README.md

comments	difficulty	edit_url	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/0500-0599/0506.Relative%20Ranks/README.md	数组 排序 堆（优先队列）

506. 相对名次

English Version

题目描述

给你一个长度为 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 <= 104
• 0 <= score[i] <= 106
• score 中的所有值 互不相同

解法

方法一

Python3

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 in range(n):
            ans[idx[i]] = top3[i] if i < 3 else str(i + 1)
        return ans

Java

class Solution {
    public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; ++i) {
            idx[i] = i;
        }
        Arrays.sort(idx, (i1, i2) -> score[i2] - score[i1]);
        String[] ans = new String[n];
        String[] top3 = new String[] {"Gold Medal", "Silver Medal", "Bronze Medal"};
        for (int i = 0; i < n; ++i) {
            ans[idx[i]] = i < 3 ? top3[i] : String.valueOf(i + 1);
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int n = score.size();
        vector<pair<int, int>> idx;
        for (int i = 0; i < n; ++i)
            idx.push_back(make_pair(score[i], i));
        sort(idx.begin(), idx.end(),
            [&](const pair<int, int>& x, const pair<int, int>& y) { return x.first > y.first; });
        vector<string> ans(n);
        vector<string> top3 = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        for (int i = 0; i < n; ++i)
            ans[idx[i].second] = i < 3 ? top3[i] : to_string(i + 1);
        return ans;
    }
};

Go

func findRelativeRanks(score []int) []string {
	n := len(score)
	idx := make([][]int, n)
	for i := 0; i < n; i++ {
		idx[i] = []int{score[i], i}
	}
	sort.Slice(idx, func(i1, i2 int) bool {
		return idx[i1][0] > idx[i2][0]
	})
	ans := make([]string, n)
	top3 := []string{"Gold Medal", "Silver Medal", "Bronze Medal"}
	for i := 0; i < n; i++ {
		if i < 3 {
			ans[idx[i][1]] = top3[i]
		} else {
			ans[idx[i][1]] = strconv.Itoa(i + 1)
		}
	}
	return ans
}