关于优先队列的问题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 巨大的时候非常有意义。比如数据无法一次性载入内存;或者数据并不是一次性已知的,而是逐渐产生的。在这种情况下,我们是无法一次性把所有元素扔进一个堆中的。这就是这种方法的意义:)
继续加油!:)
022020-09-03
相似问题