-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
347. Top K Frequent Elements.go
56 lines (47 loc) · 1.07 KB
/
347. Top K Frequent Elements.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package leetcode
import "container/heap"
func topKFrequent(nums []int, k int) []int {
m := make(map[int]int)
for _, n := range nums {
m[n]++
}
q := PriorityQueue{}
for key, count := range m {
heap.Push(&q, &Item{key: key, count: count})
}
var result []int
for len(result) < k {
item := heap.Pop(&q).(*Item)
result = append(result, item.key)
}
return result
}
// Item define
type Item struct {
key int
count int
}
// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
// 注意:因为golang中的heap是按最小堆组织的,所以count越大,Less()越小,越靠近堆顶.
return pq[i].count > pq[j].count
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
// Push define
func (pq *PriorityQueue) Push(x interface{}) {
item := x.(*Item)
*pq = append(*pq, item)
}
// Pop define
func (pq *PriorityQueue) Pop() interface{} {
n := len(*pq)
item := (*pq)[n-1]
*pq = (*pq)[:n-1]
return item
}