leetcode 347. 前 K 个高频元素

[xxleyi]

题：

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

 
示例 1:

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

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

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解：

本质还是排序，综合各种情况的话，最佳方案是堆排序。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */


// counter and sort
var topKFrequent = function(nums, k) {
  const counter = new Map()
  for (let e of nums) {
    if (counter.has(e)) {
      counter.set(e, counter.get(e) + 1)
    } else {
      counter.set(e, 1)
    }
  }
  return ([...new Set(nums)]).sort((a, b) => counter.get(b) - counter.get(a)).slice(0, k)
};

// counter and top K heap
var topKFrequent = (nums, k) => {
  const counter = new Map(), heap = Array(k + 1)
  for (let num of nums) {
    if(counter.has(num)) counter.set(num, counter.get(num) + 1)
    else counter.set(num, 1)
  }
    
  // 如果元素数量小于等于 k
  if(counter.size <= k) {
    return [...counter.keys()]
  }

  // 原地建堆，从后往前，自上而下式建小顶堆
  const buildHeap = () => {
    // 从最后一个非叶子节点开始堆化
    for (let i = k / 2 | 0; i > 0; i--) {
      heapify(i)
    }
  }

  // 堆化
  const heapify = (i) => {
    // 自上而下式堆化
    while (true) {
      let top = i
      const left = 2 * i, right = 2 * i + 1

      if (shouldUpdateTop(left, top)) {
        top = left
      }
      if (shouldUpdateTop(right, top)) {
        top = right
      }

      if (top !== i) {
        swap(i, top)
        i = top
      } else {
        break
      }
    }
  }

  // 判断是否需要更新最小索引
  const shouldUpdateTop = (i, top) => i <= k && counter.get(heap[i]) < counter.get(heap[top])

  // 交换
  const swap = (i , j) => {
    [heap[i], heap[j]] = [heap[j], heap[i]]
  }
    

  let i = 0
  const iterator = counter.entries()

  // 先填满堆
  while (i++ < k) {
    heap[i] = iterator.next().value[0]
  }

  // 然后初始化堆
  buildHeap()

  // 再遍历所有剩余元素，更新堆
  for (const [key, value] of iterator) {
    // 使用 index 1 作为堆顶，计算较为方便
    if (value > counter.get(heap[1])) {
      // 重新堆化
      heap[1] = key
      heapify(1)
    }
  }

  // 返回堆中元素
  return heap.slice(1)
};


// counter and bucket sort
var topKFrequent = function (nums, k) {
  let counter = new Map()
  for (let num of nums) {
    if (counter.has(num)) counter.set(num, counter.get(num) + 1)
    else counter.set(num, 1)
  }

  // 桶排序
  const bucketSort = () => {
    let arr = Array(nums.length + 1)
    for (const [key, value] of counter.entries()) {
      // 利用映射关系（出现频率作为下标）将数据分配到各个桶中
      if (!arr[value]) {
        arr[value] = [key]
      } else {
        arr[value].push(key)
      }
    }
    return arr
  }

  const res = [], arr = bucketSort()
  // 倒序遍历获取出现频率最大的前k个数
  for (let i = arr.length - 1; i > 0 && res.length < k; i--) {
    if (arr[i]) {
      res.push(...arr[i])
    }
  }
  return res
};