LeetCode 1122. 数组的相对排序：JavaScript 计数排序解法

题目链接

LeetCode 1122: https://leetcode-cn.com/problems/relative-sort-array

首先我们一起来看题目：

解题思路

这是一道排序的题目，那么我们首先应该想到一些常见的排序算法。主要分为两类，一类是基于比较的排序算法，例如快速排序和堆排序等。另一类是非基于比较的排序算法，包括计数排序和桶排序等。基于比较的排序算法的最优化时间复杂度也无法小于 。而非基于比较的排序算法则可以实现更低的时间复杂度。

基于比较的排序算法应用场景更广泛，而非基于比较的排序算法有自己的局限性，只适用于有条件限制的场景，例如限制了元素大小等。而本题正是限制了数组长度和元素大小，因此联想到计数排序。

本题解不对计数排序进行详细介绍，如果你看不懂题解，可以去查找相关资料学习，但我会尽可能地将题解写得更简单易懂。

解法如下：

首先要全面理解题目的要求和意图，我们需要将 arr1 中的元素按照arr2  的顺序进行排列，并且仅存在于arr1  中的元素，需要按照从小到大的顺序放在  arr1的末尾。

因为arr1  中每个元素的出现次数不一定，所以我们首先遍历arr1 ，统计其中每个元素的出现次数，并记录在 arr 中， arr中元素的下标为  arr1中被统计元素的值，arr 是我们的一个中间数组。例如arr 1 中值为 2 的元素出现了 3 次，那么我们统计之后得到 arr[2]=3。

接下来遍历arr2 ，假设 arr2中的元素为 num，那么如果 arr[num] !== 0，则说明 arr1 中还有值为 num 的元素没有被排序，那么我们就可以 ans.push(num)，同时 arr[num]--。这样就完成了按照 arr2 中元素的顺序对arr1  中的元素进行排序。

最后遍历arr ，将在arr1  中，但不在arr2  中的元素按照从小到大的顺序，附加到ans  的末尾，最后返回 ans 即可得到排序后的数组。

根据题意可知，数组长度范围固定，所以可以声明固定长度的中间数组，我使用 new Int8Array(1001) 声明  Int型的数组。这里设定其长度为 1001 是因为，数组  arr的下标与 arr1 中元素的值相对应，而其元素最大值为1000 。

代码

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function(arr1, arr2) {
    let arr = new Int8Array(1001);
    let ans = [];
    for (let i = 0; i < arr1.length; i++) {
        arr[arr1[i]]++;
    }
    for (let num of arr2) {
        while (arr[num] !== 0) {
            ans.push(num);
            arr[num]--;
        }
    }
    for (let i = 0; i < arr.length; i++) {
        while (arr[i] !== 0) {
            ans.push(i);
            arr[i]--;
        }
    }
    return ans;
};

复杂度分析：

• 时间复杂度：
• 空间复杂度：

其中  n为数组  的长度，m 为数组  的长度。