Lt1122. 数组的相对排序

1122. 数组的相对排序

给你两个数组，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]

提示：

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• arr2 中的元素 arr2[i] 各不相同
• arr2 中的每个元素 arr2[i] 都出现在 arr1 中

思路

遍历两次+额外空间存储数组

遍历 arr2，统计 arr1 中出现的数量加入结果数组中，并删除 arr1 中对应的元素。返回结果数组和剩余按升序排列过的 arr1 数组。

哈希表

还是遍历两次，第二次遍历的是 arr1 排序后的数组。遍历后根据 map 的 key 和 value 生成新数组放回。

改造 sort 函数

如果 x 和 y 都不在 arr2 中，则返回 x-y，则是未出现的元素在数组最后升序排列的判断过程。
如果 x 在 y 中有一个不在 arr2 中，则直接返回大于等 0 的数，不改变顺序即可。
如果 x 和 y 都在 arr2 中吗，则返回 arr2.indexOf(x) - arr2.indexOf(y)，根据 arr2 中的顺序排序。

解答

遍历两次+额外空间存储数组

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
  const res = [];
  for (const arr of arr2) {
    for (let i = 0; i < arr1.length; i++) {
      if (arr1[i] === arr) {
        res.push(arr);
        arr1.splice(i, 1);
        i--;
      }
    }
  }
  return res.concat(arr1.sort((a, b) => a - b));
};

哈希表

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
  const map = new Map();
  for (const arr of arr2) map.set(arr, 0);
  for (const arr of arr1.sort((a, b) => a - b))
    map.set(arr, map.has(arr) ? map.get(arr) + 1 : 1);
  return [...map.entries()].reduce(
    (a, b) => a.concat(new Array(b[1]).fill(b[0])),
    []
  );
};

改造 sort 函数

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
  return arr1.sort((x, y) => {
    if (arr2.indexOf(x) === -1 && arr2.indexOf(y) === -1) return x - y;
    else if (arr2.indexOf(x) === -1 || arr2.indexOf(y) === -1) return 1;
    else return arr2.indexOf(x) - arr2.indexOf(y);
  });
};