首页 > itarticle > 算法笔记: 力扣#506 相对名次

算法笔记: 力扣#506 相对名次

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def findRelativeRanks(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        ranks = {num:r+1 for r, num in enumerate(sorted(nums, reverse=True))}
        map_rank = lambda r : ["Gold Medal", "Silver Medal", "Bronze Medal"][r-1] if r <= 3 else str(r)
        return [map_rank(ranks[num]) for num in nums]

Java 实现

class  {
    public String[] findRelativeRanks(int[] nums) {
        int[] c_nums = nums.clone();
        Arrays.sort(c_nums);
        Map<Integer, Integer> ranks = new HashMap<>();
        for(int i = c_nums.length - 1; i >= 0; i--){
            ranks.put(c_nums[i], c_nums.length-i);
        }
        String[] medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        String[] ans = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            int r = ranks.get(num);
            if(r<=3){
                ans[i] = medals[r-1];
            }else{
                ans[i] = r+"";
            }
        }
        return ans;
    }
}

时间复杂度

O(nlogn).

空间复杂度

O(n).

链接

506. Relative Ranks
506. 相对名次
 (English version) Algorithm Notes: Leetcode#506 Relative Ranks