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

来源:6-7 优先队列相关的算法问题 Top K Frequent Elements

Corrots521

2020-09-02

老师,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
}
写回答

1回答

liuyubobobo

2020-09-03

没毛病。


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


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

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


继续加油!:)

0
2
liuyubobobo
回复
Corrots521
赞。那你整体的操作是 O(n + klogn) 的:)
2020-09-03
共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程