🍗[LeetCode]Ar506. 相对名次 【Arrays.sort、Arrays.binarySearch 查找数字、System.arraycopy 数组拷贝】

🚩传送门：https://leetcode-cn.com/problems/relative-ranks/

🍗鸡腿知识点：

1. System.arraycopy(nums, 0, array, 0, n) 数组拷贝

从 源数组nums 下标 0 开头拷贝 n 个元素放入 目标数组array 下标 0开头里

• Object src : 源数组 [ nums ]
• int srcPos : 从源数组的起始位置开始 [ 0 ]
• Object dest : 目标数组 [ array ]
• int destPos : 目标数组的开始起始位置 [ 0 ]
• int length : 要copy的数组的长度 [ n ]　
  1. Arrays.sort(array) 调用排序 API
  2. Arrays.binarySearch(array, num) 在数组 array 中查找 num
  3. TreeMap 是按照升序进行排序的，先取出来的数值最小。
  4. 🚩计数排序

题目

给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，”银牌” 和 “铜牌”（”Gold Medal”, “Silver Medal”, “Bronze Medal”）。

(注：分数越高的选手，排名越靠前。)

示例 1:

输入: [5, 4, 3, 2, 1] 输出: [“Gold Medal”, “Silver Medal”, “Bronze Medal”, “4”, “5”] 解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，”银牌”和”铜牌” (“Gold Medal”, “Silver Medal” and “Bronze Medal”). 余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。

解题思路：排序 + 二分查找

要知道成绩的排名，对成绩进行排序。首先拷贝成绩数组并对其进行排序，接着使用二分查找，查找每个成绩排第几名即可。

复杂度分析

时间复杂度：

其中 是数组的长度，需要排序数组一次。

空间复杂度：或者。

空间复杂度取决于使用的排序算法，根据是否进行原地排序（即不使用额外的数组进行临时存储）。

官方代码

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        int[] array = new int[n];
        // 1.拷贝数组
        System.arraycopy(nums, 0, array, 0, n);
        // 2.对数组进行排序
        Arrays.sort(array);
        String[] result = new String[n];
        for (int i = 0; i < n; i++) {
            // 3.利用二分查找,查找当前成绩排第几名
            int index = n - Arrays.binarySearch(array, nums[i]);
            // 4.数字越大越靠后
            switch (index) {
                case 1:
                    result[i] = "Gold Medal";
                    break;
                case 2:
                    result[i] = "Silver Medal";
                    break;
                case 3:
                    result[i] = "Bronze Medal";
                    break;
                default:
                    result[i] = String.valueOf(index);
            }
        }
        return result;
    }
}

解题思路：TreeMap

使用 TreeMap 来实现对成绩得到排序，key 存储成绩，value 存储成绩在数组中的下标。TreeMap 是按照升序进行排序的，所以在遍历集合时，通过计算可以得出当前成绩的排名。

官方代码

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        String[] result = new String[n];
        //1.key 为成绩，value 为成绩在数组中的下标，TreeMap 是按照升序进行排序的
        Map<Integer, Integer> map = new TreeMap<>();
        //2.将nums数组中的数字存入map
        for (int i = 0; i < n; i++) {
            map.put(nums[i], i);
        }
        int count = 0;
        //3.从map键值对集合中依次取出键值[先取出来的数值小,排名靠后]
        for (Map.Entry<Integer, Integer> set : map.entrySet()) {
            //4.计算成绩的排名
            int ranking = n - count++;
            switch (ranking) {
                case 1:
                    result[set.getValue()] = "Gold Medal";
                    break;
                case 2:
                    result[set.getValue()] = "Silver Medal";
                    break;
                case 3:
                    result[set.getValue()] = "Bronze Medal";
                    break;
                default:
                    result[set.getValue()] = String.valueOf(ranking);
            }
        }
        return result;
    }
}

解题思路：计数排序

扫盲：解释何为计数排序 计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。这是一种牺牲空间换取时间的做法，而且当O(k)>O(n·log(n))的时候其效率反而不如基于比较的排序。

先假设20个随机整数的值是：9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9 让我们先遍历这个无序的随机数组，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。

1. 比如第一个整数是9，那么数组下标为9的元素加1：

1. 第二个整数是3，那么数组下标为3的元素加1：

1. 继续遍历数列并修改数组……
2. 最终，数列遍历完毕时，数组的状态如下：

数组中的每一个值，代表了数列中对应整数的出现次数。 有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次： 0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10 显然，这个输出的数列已经是有序的了。 初始的数组相当于桶，越靠后面的桶越大，桶中数字代表次数，此排序最好数字在一定范围且间隔密集。

1. 寻找数组中最大的值（成绩最高的），创建一个 int[] array = new int[max + 1]的数组用来做 桶

   此数组用来实现计数排序，但是其中存储的不是次数，而是原数组中的位置，array 数组的下标对应成绩（桶越靠后数越字大，数越大优先级越高），由于 array 数组的值默认为 0（桶间隔没有的数也是0），所以在存储成绩的下标时，应对下标加 1，取时减 1 即可。

2. 倒序遍历桶，桶中存储相应位置，开始的最大，逐渐递减，保存结果。

官方代码

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        String[] result = new String[n];
        int max = 0;
        //1.找出最高的成绩
        for (int num : nums) {
            if (max < num) {
                max = num;
            }
        }
        //2.new 出排序的桶,
        int[] array = new int[max + 1];
           //3.依次遍历数组中的数,将其是nums中的第几个数存入对应桶中
        for (int i = 0; i < n; i++) {
            array[nums[i]] = i + 1;
        }
        //4.倒序遍历桶,桶越靠后,成绩越好
        int count = 1;
        for (int i = array.length - 1; i >= 0; i--) {
            //5.由于桶的个数由最大的数字决定, 不可避免有0值
            if (array[i] != 0) {
                //6.由于是第几个数,因此减去1才是其在nums中的下标 
                switch (count) {
                    case 1:
                        result[array[i] - 1] = "Gold Medal";
                        break;
                    case 2:
                        result[array[i] - 1] = "Silver Medal";
                        break;
                    case 3:
                        result[array[i] - 1] = "Bronze Medal";
                        break;
                    default:
                        result[array[i] - 1] = String.valueOf(count);
                }
                count++;
            }
        }
        return result;
    }
}