[LeetCode] 1122. Relative Sort Array

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

Example 1:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

Example 2:
Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]

Constraints:
1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
All the elements of arr2 are distinct.
Each arr2[i] is in arr1.

数组的相对排序。

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

思路

思路是用 counting sort（计数排序）做，用一个长度为 1001（Java需要定义长度）的数组（bucket）记录每个数字在 arr1 中出现的次数，然后根据数字在 arr2 中出现与否来改动arr1，使得在 arr2 中有的数字在 arr1 中能按照他们的相对顺序重新排列；再次扫描 bucket，把 arr1 中有但是 arr2 中没有的元素添加到 arr1 的末端。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] map = new int[1001];
        for (int num : arr1) {
            map[num]++;
        }

        int index = 0;
        for (int num : arr2) {
            while (map[num] != 0) {
                arr1[index++] = num;
                map[num]--;
            }
        }

        for (int i = 0; i < map.length; i++) {
            while (map[i] != 0) {
                arr1[index++] = i;
                map[i]--;
            }
        }
        return arr1;
    }
}

JavaScript实现

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
    let bucket = {};
    let res = [];
    for (let i = 0; i < arr1.length; i++) {
        if (bucket[arr1[i]]) {
            bucket[arr1[i]]++;
        } else {
            bucket[arr1[i]] = 1;
        }
    }
    for (let j = 0; j < arr2.length; j++) {
        while (bucket[arr2[j]]) {
            res.push(arr2[j]);
            bucket[arr2[j]]--;
        }
    }
    for (let key in bucket) {
        while (bucket[key]) {
            res.push(key);
            bucket[key]--;
        }
    }
    return res;
};