LeetCode506-Relative Ranks

题目

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”.

Example:

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". 
For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

  1. N is a positive integer and won’t exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.

分析

解法一:选择排序

这道题思路还是很明确的,既然要根据这些运动员的成绩排出名次,那必然需要进行对成绩关键字降序排序。但有个小地方需要注意:就是题目要求的最后填写的名次,是在原始数组中该运动员对应位置写上名次,那么我们在排序之前就需要用HashMap记录一下得分为X的运动员在原始数组中的位置。那么排序自然成了该题的关键,由于关键字互异,因此不用考虑排序稳定性的问题,而冒泡又涉及频繁的交换自然效率较低,所以我们在解法一中采用\(O({n^2})\)的选择排序,运行时间为54ms,击败了21%的人。

解法二:快排序

显然选择排序时间复杂度太大了,所以我们这次换用\(O(n\log n)\)的快速排序,这次的运行时间降为了17ms,击败了88%的人。

解法三:Arrays.sort()排序

最好的排序是直接采用JDK自带的Arrays.sort(nums, Collections.reverseOrder())进行,它是融合多种算法,根据不同数据量规模,进行了优化处理的排序算法,但主要仍以快排序为主。由于LeetCode的Java编译器版本似乎不支持Comaprator和Collections,所以本文得不到最终的运行时间。

代码

解法一

public class Solution {
    public String[] findRelativeRanks(int[] nums) {

        HashMap<Integer, Integer> posMap = new HashMap<Integer, Integer>(); //记录数字位置
        for (int i = 0; i < nums.length; i++)
            posMap.put(nums[i], i);
        
        //排序
        selectionSort(nums);
        //quickSort(nums);
        
        //填写名次
        String[] ranks = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int pos = posMap.get(nums[i]); //获取nums[i]在原始数组中的位置
            switch(i){
                case 0: ranks[pos] = "Gold Medal";break;
                case 1: ranks[pos] = "Silver Medal";break;
                case 2: ranks[pos] = "Bronze Medal";break;
                default:ranks[pos] = Integer.toString(i+1);break;
            }
        }
        
        return ranks;
    }
    
    //选择排序(降序)
    void selectionSort(int[] nums){
        
        for(int i = 0; i < nums.length - 1; i++)
        {
            int max = nums[i]; //该轮最大值
            int pos = i; //最大值所在下标
            for (int j = i + 1; j < nums.length; j++){
                if (nums[j] > max) {
                    max = nums[j];
                    pos = j;
                }
            }
            swap(nums, i, pos);
        }
    }
    
    //交换数组nums中i和j元素
    void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

解法二

// 快速排序
void quickSort(int[] seq) {
    quickSortInInterval(seq, 0, seq.length - 1); // 指定区间排序
}
// 按规定区间low-high对seq进行快速排序
void quickSortInInterval(int[] seq, int low, int high) {
    if (low < high) {
        int mid = getMiddle(seq, low, high);
        quickSortInInterval(seq, low, mid - 1); // 对左半区间快排序
        quickSortInInterval(seq, mid + 1, high); // 对右半区间快排序
    }
}
// 获取枢轴落脚位置
int getMiddle(int[] seq, int low, int high) {
    int privotKey = seq[low]; // 枢轴值
    while (low < high) {
        while (low < high && seq[high] <= privotKey)
            high--;
        seq[low] = seq[high]; // 移至低位
        while (low < high && seq[low] >= privotKey)
            low++;
        seq[high] = seq[low]; // 移至高位
    }
    seq[low] = privotKey; // 枢轴归位
    return low;
}

Leave a Comment.