LeetCode 506.相对名次

LeetCode 506.相对名次

• 标签：数组、排序、堆（优先队列）

• 难度：简单

506.相对名次

描述：给定一个长度为 n 的数组 score。其中 score[i] 表示第 i 名运动员在比赛中的成绩。所有成绩互不相同。

要求：找出他们的相对名次，并授予前三名对应的奖牌。前三名运动员将会被分别授予「金牌（"Gold Medal"）」，「银牌（"Silver Medal"）」和「铜牌（"Bronze Medal"）」。

说明：

• n == score.length。

• 1 <= n <= 10^4。

• 0 <= score[i] <= 10^6。

• score 中的所有值互不相同。

示例：

• 示例 1：

输入：score = [5,4,3,2,1]
输出：["Gold Medal","Silver Medal","Bronze Medal","4","5"]
解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。

• 示例 2：

输入：score = [10,3,8,9,4]
输出：["Gold Medal","5","Bronze Medal","Silver Medal","4"]
解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。

思路

1.对原数组进行排序（可以是升序或者降序）

2.然后根据有序的数组，再赋值"Gold Medal","Silver Medal","Bronze Medal"。

public String[] findRelativeRanks(int[] score) {
        String[] medal = new String[]{"Gold Medal","Silver Medal","Bronze Medal"};
        int[] arr = score.clone();
        bubbleSort(arr);
        Map<Integer, Integer> map = new HashMap();
        int n = score.length;
        for(int i = n-1; i >= 0; i--){
                map.put(arr[i], n-1-i);
        }
        String[] answer = new String[n];
        for(int i=0; i<n; i++){
                int order = map.get(score[i]);
                String res = order < 3 ? medal[order] : String.valueOf(order + 1);
                answer[i] = res;
        }
        return answer;
}

public static void bubbleSort(int[] arr){
        for(int i=0; i<arr.length - 1; i++){
                boolean flag = false;
                for(int j=0; j<arr.length - 1 - i; j++){
                        if(arr[j] > arr[j+1]){
                                flag = true;
                                int temp = arr[j];
                                arr[j] = arr[j+1];
                                arr[j+1] = temp;
                        }
                }
                if(! flag){
                        break;
                }
        }
}

506.相对名次