LeetCode算法题-Relative Ranks（Java实现）

佚名 5年前 (2019-02-13) 算法 1496人围观抢沙发百度已收录

这是悦乐书的第248次更新，第261篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第115题（顺位题号是506）。根据N名运动员的得分，找到他们的相对等级和得分最高的三个人，他们将获得奖牌：“金牌”，“银牌”和“铜牌”。例如：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入：[5,4,3,2,1]

输出：["Gold Medal","Silver Medal","Bronze Medal","4","5"]

说明：前三名运动员获得前三名最高分，因此获得“Gold Medal”，“Silver Medal”和“Bronze Medal”。对于剩下的两名运动员，你只需要根据他们的分数输出他们的相对等级。

注意：

N是正整数，不超过10,000。
所有运动员的得分都保证是独一无二的。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

这道题除了要排名外，还需要保持原来元素所在的位置不变，也就要求我们要把原数组中各元素的位置先保存起来。对此，我们可以使用HashMap来保存，key为元素值，value为其坐标。然后将数组排序，因为排序后是升序，所以需要我们反过来，从后往前开始排名，而新数组中的索引即为当前元素在map中的value值。

此解法的空间复杂度是O(n)，时间复杂度是O(n log(n))。

public String[] findRelativeRanks(int[] nums) {
    String[] arr = new String[nums.length];
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for (int i=0; i<nums.length; i++) {
        map.put(nums[i], i);
    }
    Arrays.sort(nums);
    for (int i=nums.length-1; i >= 0; i--) {
        if (i == nums.length-1) {
            arr[map.get(nums[i])] = "Gold Medal";
        } else if (i == nums.length-2) {
            arr[map.get(nums[i])] = "Silver Medal";
        } else if (i == nums.length-3) {
            arr[map.get(nums[i])] = "Bronze Medal";
        } else {
            arr[map.get(nums[i])] = (nums.length-i)+"";
        }
    }
    return arr;
}

03 第二种解法

对于上面的解法，我们可以使用一个新的数组来代替HashMap，将原来的数组复制一份出来，然后对复制出来的数组进行排序，然后遍历原数组的元素，使用二分法查找当前元素在复制数组中的索引，再使用数组长度减1后再减去该索引，得到当前元素的排名，然后按照金银铜以及名次的顺序依次写入字符串结果数组中去，并返回。

此解法的时间复杂度是O(n log2n)，空间复杂度是O(n)。

public String[] findRelativeRanks2(int[] nums) {
    String[] arr = new String[nums.length];
    int[] copy = nums.clone();
    Arrays.sort(copy);
    for (int i=0; i< nums.length; i++) {
        int rank = nums.length - 1 - Arrays.binarySearch(copy, nums[i]);
        if (rank == 0) {
            arr[i] = "Gold Medal";
        } else if (rank == 1) {
            arr[i] = "Silver Medal";
        } else if (rank == 2) {
            arr[i] = "Bronze Medal";
        } else {
            arr[i] = (rank+1)+"";
        }
    }
    return arr;
}

04 第三种解法

我们也可以不对原数组进行排序，而使用一个新数组来保存原数组中各元素的索引值。

先遍历原数组找到最大元素的值，然后创建一个整型包装类数组，长度为最大值加1，然后再遍历一次原数组，新数组使用原数组的元素值作为索引，值为从0开始递增的整数。然后遍历新数组，因为新数组的长度是最大值加1，所以第一名肯定是新数组的最后一位元素。

因此我们从后往前开始遍历，同时还要借助一个新索引变量，作为结果数组的递增索引，如果当前元素不为null，并且新索引等于0,1,2，那么就按照金银铜的顺序写入结果数组，剩下的将新索引加1然后转为字符串写入结果数组即可。最后返回结果数组。

至于当中使用包装类来做数组(其原始值为null)，是因为可以避免索引0的冲突，当然使用int(其原始值为0)也可以，但是需要在原索引的基础上加1，然后循环判断的时候就需要判断是否不等于0，在找到值后还需要再减1，还原成原来的索引值，而使用包装类就没这么麻烦。

此解法的时间复杂度是O(n)，其中n为数组中最大元素的值，而非元素个数，因为使用了新数组，新数组的长度是数组中最大元素加1，空间复杂度是O(n)。

public String[] findRelativeRanks3(int[] nums) {
    String[] arr = new String[nums.length];
    int max = -1;
    for (int num : nums) {
        if (num > max) {
            max = num;
        }
    }
    Integer[] numIndex = new Integer[max+1];
    for (int i=0; i<nums.length; i++) {
        numIndex[nums[i]] = i;
    }
    int index = 0;
    for (int i=numIndex.length-1; i>=0; i--) {
        if (numIndex[i] != null) {
            if (index == 0) {
                arr[numIndex[i]] = "Gold Medal";
            } else if (index == 1) {
                arr[numIndex[i]] = "Silver Medal";
            } else if (index == 2) {
                arr[numIndex[i]] = "Bronze Medal";
            } else {
                arr[numIndex[i]] = (index+1)+"";
            }
            index++;
        }
    }
    return arr;
}