347.前 K 个高频元素

题目

LeetCode 中等

INFO

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例：
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

输入: nums = [1], k = 1
输出: [1]

题解

方法：map + sort

O(nlogn) O(map 的长度)

function topKFrequent(nums: number[], k: number): number[] {
  // 统计出现次数
  const map = new Map()
  const len = nums.length
  for (let i = 0; i < len; i++) {
    const val = nums[i]
    map.set(val, (map.get(val) || 0) + 1)
  }

  console.log(map)

  // 对次数进行排序然后输出前 k 个
  return [...map.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(a => a[0])
}

const nums = [1, 1, 1, 2, 2, 3],
  k = 2
console.log('🌰', topKFrequent(nums, k))

方法：堆排序

O(nlogk) O(n)

function topKFrequentHeap(nums: number[], k: number): number[] {
  //计算次数
  let nlen = nums.length
  const map = new Map()
  for (let i = 0; i < nlen; i++) {
    const val = nums[i]
    map.set(val, (map.get(val) || 0) + 1)
  }

  console.log(map)

  //以map建堆
  const list = [...map.entries()]
  let heapSize = list.length
  let llen = list.length
  buildMaxHeap(list, heapSize)

  console.log(
    'init maxHeap',
    list.map(a => a.toString()),
  )

  //把堆顶下沉，并重新调整堆，一步步重复
  for (let i = llen - 1; i >= llen - k; i--) {
    swap(list, 0, i)
    --heapSize
    maxHeapify(list, 0, heapSize)

    console.log(
      i,
      list.map(a => a.toString()),
    )
  }

  return list.slice(-k).map(a => a[0])

  // 自下而上构建一颗大顶堆
  function buildMaxHeap(list: number[][], heapSize: number): void {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(list, i, heapSize)
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(list: number[][], i: number, heapSize: number): void {
    let l = i * 2 + 1
    let r = i * 2 + 2
    let largest = i
    if (l < heapSize && list[l][1] > list[largest][1]) {
      largest = l
    }
    if (r < heapSize && list[r][1] > list[largest][1]) {
      largest = r
    }
    if (largest !== i) {
      swap(list, i, largest)
      maxHeapify(list, largest, heapSize)
    }
  }
  //交换
  function swap(arr: number[][], i: number, j: number) {
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
}

const nums2 = [1, 10, 3, 8, 10, 9, 1, 4],
  k2 = 2
console.log('🌰', topKFrequentHeap(nums2, k2))

方法：快排的优化版

O(n) O(n)

function topKFrequentQuickSort(nums: number[], k: number): number[] {
  const map = new Map()
  const len = nums.length
  for (let i = 0; i < len; i++) {
    const val = nums[i]
    map.set(val, (map.get(val) || 0) + 1)
  }

  const list = [...map.entries()]
  return quickSort(0, list.length - 1).map((a: number[]) => a[0])

  function quickSort(left: number, right: number) {
    console.log(list.map(i => i.toString()))

    if (list.length <= 1) return list

    let pivotIndex = left //选择的中值
    let pivotNum = list[pivotIndex][1]

    console.log(
      'left',
      left,
      'right',
      right,
      'k',
      k,
      'pivotIndex',
      pivotIndex,
      'pivot',
      list[pivotIndex],
    )

    if (left < right) {
      //与中值比较，大的往前放，小的往后放
      for (let i = left + 1; i <= right; i++) {
        if (list[i][1] >= pivotNum) {
          // 碰到大于等于的值，先前进一步
          pivotIndex++
          /**
           * i > pivotIndex 就是往后push的意思
           * i === pivotIndex ，当前和前一个交换
           * */
          if (i > pivotIndex) {
            ;[list[pivotIndex], list[i]] = [list[i], list[pivotIndex]]
          } else {
            ;[list[pivotIndex - 1], list[i]] = [list[i], list[pivotIndex - 1]]
          }
        }
      }

      console.log(
        'after sort, pivotIndex',
        pivotIndex,
        list.map(a => a.toString()),
      )
      console.log('------')
    }

    if (pivotIndex === k - 1) {
      return list.slice(0, k)
    } else if (pivotIndex > k) {
      return quickSort(left, pivotIndex)
    } else {
      return quickSort(pivotIndex + 1, right)
    }
  }
}

const nums3 = [1, 10, 7, 3, 8, 1, 7, 1, 3],
  k3 = 3
// const nums3 = [1, 1, 1, 2, 2, 3],
//  k3 = 2
const res = topKFrequentQuickSort(nums3, k3)
console.log('🌰', res)