1122.数组的相对排序.md

1122.数组的相对排序

/*
 * @lc app=leetcode.cn id=1122 lang=typescript
 *
 * [1122] 数组的相对排序
 */

// @lc code=start
function relativeSortArray(arr1: number[], arr2: number[]): number[] {}
// @lc code=end

解法 1: 基础排序

选择排序

• 优先级
  • 在 arr2 中的元素比不在 arr2 中的元素更靠前
  • 如果都在 arr2 中,则在 arr2 中索引较小者更靠前
  • 如果都不再 arr2 中,则值较小者更靠前

function relativeSortArray(arr1: number[], arr2: number[]): number[] {
  const map: { [key: number]: number } = {}
  for (let i = 0; i < arr2.length; i++) {
    map[arr2[i]] = i
  }
  const compare = (i: number, j: number) => {
    if (map.hasOwnProperty(arr1[i])) {
      // 如果都在 arr2 中,则在 arr2 中索引较小者更靠前
      if (map.hasOwnProperty(arr1[j])) return map[arr1[i]] >= map[arr1[j]]
      // 在 arr2 中的元素比不在 arr2 中的元素更靠前
      return false
    } else if (map.hasOwnProperty(arr1[j])) return true
    // 如果都不再 arr2 中,则值较小者更靠前
    else return arr1[i] >= arr1[j]
  }

  const swap = (i: number, j: number) => {
    ;[arr1[i], arr1[j]] = [arr1[j], arr1[i]]
    return j
  }

  for (let i = 0; i < arr1.length; i++) {
    let min = i
    for (let j = i + 1; j < arr1.length; j++) {
      min = compare(min, j) ? j : min
    }
    swap(min, i)
  }
  return arr1
}

插入排序

function relativeSortArray(arr1: number[], arr2: number[]): number[] {
  const map: { [key: number]: number } = {}
  for (let i = 0; i < arr2.length; i++) {
    map[arr2[i]] = i
  }
  const compare = (i: number, j: number) => {
    if (map.hasOwnProperty(arr1[i])) {
      if (map.hasOwnProperty(arr1[j])) return map[arr1[i]] >= map[arr1[j]]
      return false
    } else if (map.hasOwnProperty(arr1[j])) return true
    else return arr1[i] >= arr1[j]
  }
  const swap = (i: number, j: number) => {
    ;[arr1[i], arr1[j]] = [arr1[j], arr1[i]]
    return j
  }

  for (let i = 0; i < arr1.length; i++) {
    let cur = i
    for (let j = i - 1; j >= 0; j--) {
      if (compare(cur, j)) break
      cur = swap(cur, j)
    }
  }
  return arr1
}

冒泡排序

function relativeSortArray(arr1: number[], arr2: number[]): number[] {
  const map: { [key: number]: number } = {}
  for (let i = 0; i < arr2.length; i++) {
    map[arr2[i]] = i
  }
  const compare = (i: number, j: number) => {
    if (map.hasOwnProperty(arr1[i])) {
      if (map.hasOwnProperty(arr1[j])) return map[arr1[i]] >= map[arr1[j]]
      return false
    } else if (map.hasOwnProperty(arr1[j])) return true
    else return arr1[i] >= arr1[j]
  }

  const swap = (i: number, j: number) => {
    ;[arr1[i], arr1[j]] = [arr1[j], arr1[i]]
    return j
  }

  for (let i = arr1.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (compare(j, j + 1)) swap(j, j + 1)
    }
  }
  return arr1
}

高级排序

快速排序

function relativeSortArray(arr1: number[], arr2: number[]): number[] {
  const map: { [key: number]: number } = {}
  for (let i = 0; i < arr2.length; i++) {
    map[arr2[i]] = i
  }
  const compare = (num1: number, num2: number) => {
    if (map.hasOwnProperty(num1)) {
      if (map.hasOwnProperty(num2)) return map[num1] > map[num2]
      return false
    } else if (map.hasOwnProperty(num2)) return true
    else return num1 > num2
  }

  const swap = (i: number, j: number) => {
    ;[arr1[i], arr1[j]] = [arr1[j], arr1[i]]
    return j
  }

  const quickSort = (arr: number[], start = 0, end = arr.length - 1) => {
    if (start >= end) return

    // mid 快排中分割左右两组的中间值,cur 左边都是比 mid 小的值
    let [mid, count] = [arr[start], start]
    for (let i = start; i <= end; i++) {
      if (!compare(mid, arr[i])) continue

      swap(count, i)
      count++
    }

    // 如果 count 还在 start 的位置,那说明右侧所有数都比 start 大,这时主动将 start 单独分出来作为一组
    if (count === start) count++

    quickSort(arr, start, count - 1)
    quickSort(arr, count, end)
  }
  quickSort(arr1)
  return arr1
}

归并排序

function relativeSortArray(arr1: number[], arr2: number[]): number[] {
  const map: { [key: number]: number } = {}
  for (let i = 0; i < arr2.length; i++) {
    map[arr2[i]] = i
  }
  const compare = (num1: number, num2: number) => {
    if (map.hasOwnProperty(num1)) {
      if (map.hasOwnProperty(num2)) return map[num1] > map[num2]
      return false
    } else if (map.hasOwnProperty(num2)) return true
    else return num1 > num2
  }

  const swap = (i: number, j: number) => {
    ;[arr1[i], arr1[j]] = [arr1[j], arr1[i]]
    return j
  }

  const mergeSort = (arr: number[], start = 0, end = arr.length - 1) => {
    if (start >= end) return

    const mid = (start + end) >> 1
    mergeSort(arr, start, mid)
    mergeSort(arr, mid + 1, end)
    const tmp: number[] = []
    let [l, r] = [start, mid + 1]
    while (l <= mid && r <= end) {
      compare(arr[l], arr[r]) ? tmp.push(arr[r++]) : tmp.push(arr[l++])
    }
    while (l <= mid) tmp.push(arr[l++])
    while (r <= mid) tmp.push(arr[r++])

    for (let i = 0; i < tmp.length; i++) arr[start + i] = tmp[i]
  }
  mergeSort(arr1)
  return arr1
}

Case

test.each([
  {
    input: {
      arr1: [2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19],
      arr2: [2, 1, 4, 3, 9, 6],
    },
    output: [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19],
  },
  {
    input: {
      arr1: [28, 6, 22, 8, 44, 17],
      arr2: [22, 28, 8, 6],
    },
    output: [22, 28, 8, 6, 17, 44],
  },
  {
    input: {
      arr1: [2, 21, 43, 38, 0, 42, 33, 7, 24, 13, 12, 27, 12, 24, 5, 23, 29, 48, 30, 31],
      arr2: [2, 42, 38, 0, 43, 21],
    },
    output: [2, 42, 38, 0, 43, 21, 5, 7, 12, 12, 13, 23, 24, 24, 27, 29, 30, 31, 33, 48],
  },
])('input: arr1 = $input.arr1, arr2 = $input.arr2', ({ input: { arr1, arr2 }, output }) => {
  expect(relativeSortArray(arr1, arr2)).toEqual(output)
})