zhangdizhangdi

347.前 K 个高频元素

题目

LeetCode 中等

给你一个整数数组 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 的长度)

js
function topKFrequent(nums, k) {
  // 统计出现次数
  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))
执行结果
Map(3) { 1 => 3, 2 => 2, 3 => 1 }
🌰 [ 1, 2 ]

方法：堆排序

O(nlogk) O(n)

js
function topKFrequentHeap(nums, k) {
  //计算次数
  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, heapSize) {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(list, i, heapSize)
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(list, i, heapSize) {
    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, i, j) {
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
}

const nums = [1, 10, 3, 8, 10, 9, 1, 4],
  k = 2
console.log('🌰', topKFrequentHeap(nums, k))
执行结果
Map(6) { 1 => 2, 10 => 2, 3 => 1, 8 => 1, 9 => 1, 4 => 1 }
init maxHeap [ '1,2', '10,2', '3,1', '8,1', '9,1', '4,1' ]
5 [ '10,2', '4,1', '3,1', '8,1', '9,1', '1,2' ]
4 [ '9,1', '4,1', '3,1', '8,1', '10,2', '1,2' ]
🌰 [ 10, 1 ]

方法：快排的优化版

O(n) O(n)

js
function topKFrequentQuickSort(nums, k) {
  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 => a[0])

  function quickSort(left, right) {
    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 nums = [1, 10, 7, 3, 8, 1, 7, 1, 3],
  k = 3
// const nums = [1, 1, 1, 2, 2, 3],
//  k = 2
const res = topKFrequentQuickSort(nums, k)
console.log('🌰', res)
执行结果
[ '1,3', '10,1', '7,2', '3,2', '8,1' ]
left 0 right 4 k 3 pivotIndex 0 pivot [ 1, 3 ]
after sort, pivotIndex 0 [ '1,3', '10,1', '7,2', '3,2', '8,1' ]
------
[ '1,3', '10,1', '7,2', '3,2', '8,1' ]
left 1 right 4 k 3 pivotIndex 1 pivot [ 10, 1 ]
after sort, pivotIndex 4 [ '1,3', '7,2', '3,2', '8,1', '10,1' ]
------
[ '1,3', '7,2', '3,2', '8,1', '10,1' ]
left 1 right 4 k 3 pivotIndex 1 pivot [ 7, 2 ]
after sort, pivotIndex 2 [ '1,3', '3,2', '7,2', '8,1', '10,1' ]
------
🌰 [ 1, 3, 7 ]