关于优先队列的问题leetcode#347

Question

老师，leetcode的这道问题，我觉得使用最大堆也是可以解决的。
将Map中记录的元素->频率键值对全部放入堆中，然后从堆中推出k个元素，不就是频率最高的k个元素么
下面是我用go实现的代码(go的heap需要自己实现下接口，代码有点多…)，leetcode提交也是OK的

func topKFrequent(nums []int, k int) []int {
	// 统计每个元素出现的频率
	freq := make(map[int]int)
	for _, v := range nums {
		freq[v]++
	}
	minHeap := &FeqMinHeap{}
	// 将记录元素->频率的所有数据对放入堆中
	for k, v := range freq {
		*minHeap = append(*minHeap, Feq{
			val:   k,
			count: v,
		})
	}
	// heapify构建堆
	heap.Init(minHeap)
	res := make([]int, k)
	// 从堆中取出k个元素即为频率最高的k个元素
	for i := 0; i < k && minHeap.Len() > 0; i++ {
		res[i] = heap.Pop(minHeap).(Feq).val
	}
	return res
}

type Feq struct {
	val   int
	count int
}

type FeqMinHeap []Feq

func (pq FeqMinHeap) Len() int {
	return len(pq)
}

func (pq FeqMinHeap) Less(i, j int) bool {
	return pq[i].count > pq[j].count
}

func (pq FeqMinHeap) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *FeqMinHeap) Push(x interface{}) {
	*pq = append(*pq, x.(Feq))
}

func (pq *FeqMinHeap) Pop() interface{} {
	n := len(*pq) - 1
	res := (*pq)[n]
	*pq = (*pq)[:n]
	return res
}

Answer 1

liuyubobobo 2020-09-03 02:15:26

没毛病。

如果使用最大堆找最大的 k 个元素，你需要将所有元素放到堆中，时间复杂度是 nlogn 的，空间复杂度是 O(n) 的。此时，其实你将数组原地排序，取前 k 个元素，更省空间：）

如果你要使用最小堆找最大的 k 个元素，你只需要在堆中记录当前看到的最小的 k 个元素。此时，时间复杂度是 O(nlogk) 的，空间复杂度是 O(k) 的。

这个思想在 n 巨大的时候非常有意义。比如数据无法一次性载入内存；或者数据并不是一次性已知的，而是逐渐产生的。在这种情况下，我们是无法一次性把所有元素扔进一个堆中的。这就是这种方法的意义：）

继续加油！：）

• 提问者 Corrots521 #1

  谢谢老师的解答，我忽略了对于海量数据的场景。
  不过这里我把所有元素放入堆中，用了heapify，时间复杂度应该是O(n)，哈哈

• liuyubobobo 回复 提问者 Corrots521 #2

  赞。那你整体的操作是 O(n + klogn) 的：）