每日leetcode-数组-506. 相对名次

标签：rgb   没有   tco   运动员   ever   nlogn   bsp   lis   silver   分类：字符串-数字与字符串间转换 题目描述： 给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（"Gold Medal", "Silver Medal", "Bronze Medal"）。 (注：分数越高的选手，排名越靠前。) 解题思路： 如果直接排序是不行的，因为会丢失老的索引。 因此我用了一个 pairs 数组，来维护一个 score-> 索引的映射。之后对 paris 进行降序排列即可。由于我事先保存了老的索引信息，因此是没有问题的。 class Solution: def findRelativeRanks(self, score: List[int]) -> List[str]: # score.sort(reverse = True) #true是降序 false是升序 pairs = [] for i in range(len(score)): pairs.append([score[i],i]) pairs.sort(key=lambda a:a[0],reverse = True) for i in range(len(score)): if i==0: score[pairs[i][1]] = "Gold Medal" if i==1: score[pairs[i][1]]="Silver Medal" if i==2: score[pairs[i][1]] = "Bronze Medal" if i > 2: score[pairs[i][1]] = str(i+1) return score     复杂度分析 时间复杂度：复杂度的话注意是排序引起的，因此为 O(NlogN)O(NlogN)空间复杂度：由于使用了 paris 数组， 因此空间复杂度为 O(N)O(N)  每日leetcode-数组-506. 相对名次标签：rgb   没有   tco   运动员   ever   nlogn   bsp   lis   silver   原文地址：https://www.cnblogs.com/LLLLgR/p/14964749.html