题目

题目来源：力扣（LeetCode）

给你两个数组，arr1 和 arr2，
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

思路分析

本题中元素的范围为 [0, 1000]，这个范围并不是很大，我们可以考虑不基于比较的排序，例如「计数排序」。

元素的取值范围是 [0, 1000]，因此我们可以使用一个长度为 1001 (下标从 0 到 1000) 的数组 counts，记录每一个元素在数组 arr1 中出现的次数;

然后遍历数组 arr2，当遍历到元素 x 时，我们将 counts[x] 个 x 加入结果数组 result 中，并将 counts[x] 清零，当遍历结束后，所有在 arr2 中出现过的元素就已经有序了。

此时还剩下没有在 arr2 中出现过的元素，因此我们还需要对整个数组 counts 进行一次遍历，当遍历到元素 x 时，如果 counts[x] 不为 0 ，我们就将 counts[x] 个 x 加入结果数组 result 中。

  1. /**
  2.  * @param {number[]} arr1
  3.  * @param {number[]} arr2
  4.  * @return {number[]}
  5.  */
  6. var relativeSortArray = function (arr1, arr2) {
  7.   // 取值范围是【0-1000】，开个大数据，取一个数1005
  8.   let arr = new Array(1001).fill(0);
  9.   let result = [];
  10.   // 记录数字出现的次数
  11.   for (let i = 0; i < arr1.length; i++) {
  12.     arr[arr1[i]] += 1;
  13.   }
  14.   // 按照arr2出现的顺序，将arr1重新归置，放到结果数组result里面
  15.   for (let i = 0; i < arr2.length; i++) {
  16.     while (arr[arr2[i]]--) {
  17.       result.push(arr2[i]);
  18.     }
  19.   }
  20.   // 剩余的数字按照从小到大的顺序放到后面
  21.   for (let i = 0; i < arr.length; i++) {
  22.     if (arr[i] <= 0) continue;
  23.     while (arr[i]--) {
  24.       result.push(i);
  25.     }
  26.   }
  28.   return result;
  29. }