Question

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 中的所有值 互不相同

解法

方法一

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

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;
  }
}

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;
  }
};

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
}