leetCode/1122.数组的相对排序.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>1122. 数组的相对排序</title>
  </head>
  <body>
    <script>
      // https://leetcode.cn/problems/relative-sort-array/

      // 给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
      // 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
      // 提示：
      // 1 <= arr1.length, arr2.length <= 1000
      // 0 <= arr1[i], arr2[i] <= 1000
      // arr2 中的元素 arr2[i]  各不相同
      // arr2 中的每个元素 arr2[i] 都出现在 arr1 中

      /**
       * @param {number[]} arr1
       * @param {number[]} arr2
       * @return {number[]}
       */
      var relativeSortArray = function (arr1, arr2) {};

      // --- answer-1 ---

      // 使用sort进行自定义排序
      var relativeSortArray = function (arr1 = [], arr2 = []) {
        const rank = arr2.reduce((pre, cur, idx) => {
          pre[cur] = idx;
          return pre;
        }, {});
        arr1.sort((a, b) => {
          if (a in rank) {
            return b in rank ? rank[a] - rank[b] : -1;
          } else {
            return b in rank ? 1 : a - b;
          }
        });
        return arr1;
      };

      // --- answer-1 ---

      // --- answer-2 ---

      // 计数， 统计数出现的次数， 多余的再进行遍历
      var relativeSortArray = function (arr1 = [], arr2 = []) {
        const result = [];
        const count = arr1.reduce((pre, cur, idx) => {
          pre[cur] = (pre[cur] || 0) + 1;
          return pre;
        }, {});
        for (let x of arr2) {
          for (let i = 0; i < count[x]; i++) {
            result.push(x);
          }
          count[x] = 0;
        }
        const max = Math.max.apply(Math, arr1);
        for (let i = 0; i <= max; i++) {
          for (let j = 0; j < count[i] || 0; j++) {
            result.push(i);
          }
        }
        return result;
      };

      // --- answer-2 ---

      var arr1 = [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19],
        arr2 = [2, 1, 4, 3, 9, 6];
      var result = [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19];

      var arr1 = [28, 6, 22, 8, 44, 17],
        arr2 = [22, 28, 8, 6];
      var result = [22, 28, 8, 6, 17, 44];

      // var arr1 = [26, 21, 11, 20, 50, 34, 1, 18];
      // var arr2 = [21, 11, 26, 20];
      // var result = [21, 11, 26, 20, 1, 18, 34, 50];

      console.log('arr1 = ', arr1);
      console.log('arr2 = ', arr2);
      console.log('result = ', result);
      console.log('result = ', relativeSortArray(arr1, arr2));
    </script>
  </body>
</html>