TNotes.leetcode

Appearance

1122. 数组的相对排序【简单】

1122. 数组的相对排序【简单】 ​

1. 📝 题目描述 ​

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

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

示例 1：

txt
输入：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]

示例 2：

txt
输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]

提示：

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

2. 🎯 s.1 - 计数法 ​

js
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
  const maxV = 1000
  const cnt = new Array(maxV + 1).fill(0)
  for (let v of arr1) cnt[v]++
  const res = []
  // 先按 arr2 的顺序取出
  for (let v of arr2) {
    while (cnt[v] > 0) {
      res.push(v)
      cnt[v]--
    }
  }
  // 再输出剩余元素（升序）
  for (let v = 0; v <= maxV; v++) {
    while (cnt[v] > 0) {
      res.push(v)
      cnt[v]--
    }
  }
  return res
}
  • 时间复杂度：O(n+K)，其中 n 为数组长度，K 为值域范围，需遍历数组并线性输出
  • 空间复杂度：O(K)，用于存储固定大小的计数数组

算法思路：

  • 统计 arr1 每个值的频次，值域固定为 0–1000
  • 先按 arr2 的顺序输出对应元素并减少频次，再按值域顺序输出剩余元素
  • 线性时间覆盖所有元素，避免排序带来的时间开销

3. 🎯 s.2 - 映射排序法 ​

js
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
  const rank = new Map()
  for (let i = 0; i < arr2.length; i++) rank.set(arr2[i], i)
  const base = arr2.length
  return arr1.slice().sort((a, b) => {
    const ra = rank.has(a) ? rank.get(a) : base + a
    const rb = rank.has(b) ? rank.get(b) : base + b
    return ra - rb
  })
}
  • 时间复杂度：O(nlog⁡n)，其中 n 为数组长度，排序过程占主导
  • 空间复杂度：O(m)，其中 m 为 arr2 长度，用于哈希表记录排名

算法思路：

  • 用哈希表为 arr2 中的元素记录相对排名
  • 自定义比较器：若两元素均有排名则按排名排序，否则按数值升序
  • base 在此的作用是给不在 arr2 中的元素一个统一的排序基准，确保它们按照自身数值大小排在 arr2 中所有元素之后

Discussions