LeetCode – 1122. 数组的相对排序

时间:2021-1-8 作者:admin

LeetCode – 1122. 数组的相对排序

题目

给你两个数组,arr1 和 arr2,

  • arr2 中的元素各不相同
  • arr2 中的每个元素都出现在 arr1 中

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

示例1:

输入: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 中

解题思路

1. 设定排序规则

  1. 遍历 arr2 数组,使用哈希表对相对顺序进行映射
  2. 设计排序规则,即比较函数

对于参与比较的元素 a , b,有以下可能:

  • a, b 均在哈希表中,比较 map[a] 与 map[b];
  • a, b 均不在哈希表中,比较 a 与 b;
  • 其他情况则出现在哈希表中的元素在前。
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function(arr1, arr2) {
    // 使用哈希表对 arr2 比较规则进行映射
    const map = {}
    for (let i = 0, l = arr2.length; i < l;i++) {
        map[arr2[i]] = i
    }
    // 设计比较函数
    function compare(a, b) {
            if (map[a] == undefined) {
            // a, b 均不在哈希表中, 比较 a 与 b
              if (map[b] == undefined) return a - b
            // 仅有 b 在表中
            return 1
        } else {
            // 仅有 a 在表中
            if (map[b] == undefined) return -1
            // a, b 都在表中, 比较 map[a] 与 map[b]
            return map[a] - map[b]
        }
    }
    // 对 arr1 进行排序操作
    return arr1.sort(compare)
};

2. 设计比较权重

  1. 遍历 arr2 数组,使用哈希表以元素索引设置比较权重
  2. 未在 arr2 数组中出现的元素因以升序排序置于 arr1 尾部,可将未出现元素的权重设置为 1000 + 自身值
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function(arr1, arr2) {
    // 使用哈希表对 arr2 元素设置比较权重
    const map = {}
    for (let i = 0, l = arr2.length; i < l;i++) {
        map[arr2[i]] = i
    }
      // 对元素的排序权重进行比较
    function compare(a, b) {
          // 将未出现元素的权重设置为 1000 + 自身值
        // 期待空值合并运算符 ??
            const weightA = map[a] >= 0? map[a]: 1000 + a
        const weightB = map[b] >= 0? map[b]: 1000 + b
        return weightA - weightB
    }
    // 对 arr1 进行排序操作
    return arr1.sort(compare)
};

3. 计数排序

  1. 记录 arr1 中每个元素的出现次数
  2. 根据 arr2 的顺序,向答案数组填充元素对应数量
  3. 遍历计数数组非零部分,填充入答案数组
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function(arr1, arr2) {
    // 优化存储空间
    const max = Math.max(...arr1)
    const frequency = new Array(max + 1).fill(0)
    // 记录 arr1 中每个元素的出现次数
    arr1.forEach(e => frequency[e] += 1)

    const ans = []
    // 根据 arr2 的顺序,向答案数组填充元素对应数量
    arr2.forEach(e => {
        while (frequency[e]) {
            ans.push(e)
            frequency[e] --
        }
    })
    // 将计数数组非零部分,填充入答案数组
    for (let i = 0, l = frequency.length; i < l; i++) {
        if (frequency[i] > 0) {
            while (frequency[i]) {
                ans.push(i)
                frequency[i] --
            }
        }
    }
    return ans
};
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。