题目描述

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".

Example 1:

Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

  1. N is a positive integer and won't exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.

解法一

思路

想要知道相对顺序,那就免不了要排序;但题目要求输出的排名是按原始元素先后顺序的,那么对于排序后的元素来说,就要建立一个元素值向原索引值的映射。

上面的描述可以用一次排序,加一个Map映射(值向索引的映射)来实现。我们考虑还有没有更简便的方法,如果只使用Map,那么因为Map的key(元素值)是无序的,所以不能得到相对顺序。那么怎样可以让Map的key是有序的呢?我们可以考虑用数组来模拟Map,数组的大小为“元素最大值”,而数组索引为元素值,索引对应的值为原元素索引,这样我们在建立了这个数组后,就只需要从后往前遍历一次数组就好了。

例如,[5, 4, 3, 2, 1]可以建立数组[0, 5, 4, 3, 2, 1],这样从后往前遍历数组遇到非0的元素值就代表此处“现索引”为“原值”,“现值”为“原索引”,即可得到相对排名,即[Gold, Silver, Bronze, 4, 5]。再例如[4, 8, 1, 3, 2, 6] -> [0, 3, 5, 4, 1, 0, 6, 0, 2] -> [Bronze, Gold, 6, 4, 5, Silver]

Python

class Solution(object):
    def findRelativeRanks(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        map = [0] * (max(nums) + 1)
        for index, num in enumerate(nums):
            map[num] = index + 1
        result = [None] * len(nums)
        rank = 1
        for i in range(len(map) - 1, -1, -1):
            index = map[i]
            if index:
                value = None
                if rank == 1:
                    value = 'Gold Medal'
                elif rank == 2:
                    value = 'Silver Medal'
                elif rank == 3:
                    value = 'Bronze Medal'
                else:
                    value = str(rank)
                result[index - 1] = value
                rank += 1
        return result

Java

public class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int maxNum = -1;
        for (int num : nums) {
            if (num > maxNum) {
                maxNum = num;
            }
        }
        int[] map = new int[maxNum + 1];
        for (int i = 0; i < nums.length; i++) {
            map[nums[i]] = i + 1;
        }
        String[] result = new String[nums.length];
        int rank = 1;
        for (int i = map.length - 1; i > -1; i--) {
            int index = map[i];
            if (index > 0) {
                String value = "";
                if (rank == 1) {
                    value = "Gold Medal";
                } else if (rank == 2) {
                    value = "Silver Medal";
                } else if (rank == 3) {
                    value = "Bronze Medal";
                } else {
                    value = String.valueOf(rank);
                }
                result[index - 1] = value;
                rank++;
            }
        }
        return result;
    }
}

C++

class Solution {
public:
    vector<string> findRelativeRanks(vector<int> &nums) {
        int maxNum = *max_element(nums.begin(), nums.end());
        vector<int> map(maxNum + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]] = i + 1;
        }
        vector<string> result(nums.size());
        int rank = 1;
        for (int i = map.size() - 1; i > -1; i--) {
            int index = map[i];
            if (index > 0) {
                string value;
                if (rank == 1) {
                    value = "Gold Medal";
                } else if (rank == 2) {
                    value = "Silver Medal";
                } else if (rank == 3) {
                    value = "Bronze Medal";
                } else {
                    value = to_string(rank);
                }
                result[index - 1] = value;
                rank++;
            }
        }
        return result;
    }
};