LeetCode（Heap)506. Relative Ranks

落日映苍穹つ 2023-09-24 22:49 31阅读 0赞

# 1.问题 #

You are given an integer array score of size n, where score\[i\] is the score of the ith athlete in a competition. All the scores are guaranteed to be unique.

The athletes are placed based on their scores, where the 1st place athlete has the highest score, the 2nd place athlete has the 2ndhighest score, and so on. The placement of each athlete determines their rank:

The 1st place athlete’s rank is “Gold Medal”.  
The 2nd place athlete’s rank is “Silver Medal”.  
The 3rd place athlete’s rank is “Bronze Medal”.  
For the 4th place to the nth place athlete, their rank is their placement number (i.e., the xth place athlete’s rank is “x”).  
Return an array answer of size n where answer\[i\] is the rank of the ith athlete.

Example 1:

Input: score = \[5,4,3,2,1\]  
Output: \[“Gold Medal”,“Silver Medal”,“Bronze Medal”,“4”,“5”\]  
Explanation: The placements are \[1st, 2nd, 3rd, 4th, 5th\].  
Example 2:

Input: score = \[10,3,8,9,4\]  
Output: \[“Gold Medal”,“5”,“Bronze Medal”,“Silver Medal”,“4”\]  
Explanation: The placements are \[1st, 5th, 3rd, 2nd, 4th\].

Constraints:

n == score.length  
1 <= n <= 104  
0 <= score\[i\] <= 106  
All the values in score are unique.

# 2. 解题思路 #

## 方法1： ##

> 1.先复制原来数据，进行排序，并定义socre长度，新建数组result  
> 2.新建map，for循环，复制的数据的值放入key，value值是排名的String值  
> 3.for循环遍历，根据score的key，取出value放入result  
> 4.返回result

## 方法2： ##

> 求分数->排名映射。  
> 最简单的方法是用score对这些分数进行排序  
> 但是我们会失去他们原来的顺序。  
> 我们可以创建 (score , original index) 对并按分数递减对它们进行排序。  
> 然后我们将有分数 -> 排名（新索引）映射  
> 我们可以使用原始索引来创建结果。

> Example:  
> nums\[i\] : \[10, 3, 8, 9, 4\]  
> pair\[i\]\[0\] : \[10, 3, 8, 9, 4\]  
> pair\[i\]\[1\] : \[ 0, 1, 2, 3, 4\]  
> After sort:  
> pair\[i\]\[0\] : \[10, 9, 8, 4, 3\]  
> pair\[i\]\[1\] : \[ 0, 3, 2, 4, 1\]

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public String[] findRelativeRanks(int[] score) {
        
           int[] clone = score.clone();//1.先复制原来数据，进行排序，并定义socre长度，新建数组result
           Arrays.sort(clone);
           int length=score.length;
           String[]result = new String[length];
           
           Map<Integer,String> map = new HashMap<>();//2.新建map，for循环，复制的数据的值放入key，value值是排名的String值
           for (int i = 0; i < length; i++) {
        
                if(i==length-1){
        
                    map.put(clone[i],"Gold Medal");
                }else if(i==length-2) {
        
                    map.put(clone[i], "Silver Medal");
                } else if (i==length-3) {
        
                    map.put(clone[i], "Bronze Medal");
    
                }else{
        
                    map.put(clone[i],String.valueOf(length-i));
                }
    
            }
            for (int i = 0; i < length; i++) {
        //3.for循环遍历，根据score的key，取出value放入result
                result[i]=map.get(score[i]);
            }
            return result;//4.返回result
        }
    }

> 解题思路基本相同

public class Solution {
        
       int[] ranks = score.clone(); //1.复制原来数据，进行排序
            Arrays.sort(ranks);
            Map<Integer, Integer> map = new HashMap<>();//2.新建map，将排序的数组为可key,value为长度-i，比如索引0（5），1（4）
            for(int i = 0; i<ranks.length; i++){
        
                map.put(ranks[i], score.length-i);
            }
            String[] res = new String[score.length];
            //3.新建数组res，for循环遍历，map的key，求value，并将值放入res
            for(int i = 0; i<score.length; i++){
        
                int rank = map.get(score[i]);
                String rankStr = rank+"";
                if(rank==1) rankStr = "Gold Medal";
                else if(rank==2) rankStr = "Silver Medal";
                else if(rank==3) rankStr = "Bronze Medal";
                res[i] = rankStr;
            }
            return res;//4.返回res
        }
    }

## 代码2： ##

public class Solution {
        
        public String[] findRelativeRanks(int[] nums) {
        
            Integer[] index = new Integer[nums.length];//1.定义数组index，for循环将index存入数组，新建result数组
            String[] result = new String[nums.length];     
            for (int i = 0; i < nums.length; i++) {
        
                index[i] = i;
            }     
            Arrays.sort(index, (a, b) -> (nums[b] - nums[a]));//2.根据索引进行排序
            for (int i = 0; i < nums.length; i++) {
        
            //3.for循环遍历，根据条件，设定value值
                if (i == 0) {
        
                    result[index[i]] = "Gold Medal";
                }
                else if (i == 1) {
        
                    result[index[i]] = "Silver Medal";
                }
                else if (i == 2) {
        
                    result[index[i]] = "Bronze Medal";
                }
                else {
        
                    result[index[i]] = (i + 1) + "";
                }
            }
    
            return result;
        }
    }

public class Solution {
        
        public String[] findRelativeRanks(int[] nums) {
        
            int[][] pair = new int[nums.length][2];
            
            for (int i = 0; i < nums.length; i++) {
        
                pair[i][0] = nums[i];
                pair[i][1] = i;
            }
            
            Arrays.sort(pair, (a, b) -> (b[0] - a[0]));
            
            String[] result = new String[nums.length];
    
            for (int i = 0; i < nums.length; i++) {
        
                if (i == 0) {
        
                    result[pair[i][1]] = "Gold Medal";
                }
                else if (i == 1) {
        
                    result[pair[i][1]] = "Silver Medal";
                }
                else if (i == 2) {
        
                    result[pair[i][1]] = "Bronze Medal";
                }
                else {
        
                    result[pair[i][1]] = (i + 1) + "";
                }
            }
    
            return result;
        }
    }