[leetcode]: 506. Relative Ranks

刺骨的言语ヽ痛彻心扉 2022-06-16 01:52 94阅读 0赞

# 1.题目描述 #

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”.  
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”.  
翻译：给出一个长度为N的运动员得分数组，求每个运动员对应的名次。  
其中1,2,3的表达为”Gold Medal”, “Silver Medal”, “Bronze Medal”

# 2.分析 #

这个题目考察的是排序并且需要知道排序后的元素原本的下标。  
大致看到三种解法：  
（1）先保存各个得分的下标。用字典。因为得分都是唯一的。再排序。  
（2）自定义比较函数，根据得分大小排序，但参与排序的是下标序列。  
（3）使用数据结构，priority\_queue  
我用python写的，采用的是第一种解法。先用字典保存元素下标再排序。

# 3.代码 #

python

def findRelativeRanks(nums):
        #记录每个分数值对应排名
        pos={n:i+1 for i,n in enumerate(sorted(nums,reverse=True))}
        def f(x):
            if pos[x]==1:
                return "Gold Medal"
            elif pos[x]==2:
                return "Silver Medal"
            elif pos[x]==3:
                return "Bronze Medal"
            else:
                return str(pos[x])
        return map(f,nums)

也有人把代码缩减到很短

def findRelativeRanks(self, nums):
        sort = sorted(nums)[::-1]
        rank = ["Gold Medal", "Silver Medal", "Bronze Medal"] + map(str, range(4, len(nums) + 1))
        return map(dict(zip(sort, rank)).get, nums)

自定义排序函数的c++解法我觉得是很赞的，这里把那位大牛的解法贴出来学习一下。

class Solution {
    public:
        vector<string> findRelativeRanks(vector<int>& nums) {
            vector<int> rank;
            for(int i=0; i<nums.size(); ++i) rank.push_back(i);
    
            sort(rank.begin(), rank.end(), [&](int a, int b){
       return nums[a] > nums[b];});
            vector<string> ranks(nums.size());
    
            for(int i=3; i<nums.size(); ++i){
                ranks[rank[i]] = std::to_string(i+1);
            }
    
            if(nums.size() > 0) ranks[rank[0]] = "Gold Medal";
            if(nums.size() > 1) ranks[rank[1]] = "Silver Medal";
            if(nums.size() > 2) ranks[rank[2]] = "Bronze Medal";
    
            return ranks;
        }
    };