Time: O(n) Space: O(n)
(nums []int, k int)
| 31 | // Time: O(n) |
| 32 | // Space: O(n) |
| 33 | func topKFrequent(nums []int, k int) []int { |
| 34 | // build map of frequencies |
| 35 | freq := make(map[int]int) |
| 36 | for _, n := range nums { |
| 37 | freq[n] += 1 |
| 38 | } |
| 39 | |
| 40 | // push frequencies into freqHeap |
| 41 | h := &freqHeap{} |
| 42 | heap.Init(h) |
| 43 | for k, v := range freq { |
| 44 | heap.Push(h, freqHeapVal{ |
| 45 | key: k, |
| 46 | val: v, |
| 47 | }) |
| 48 | } |
| 49 | |
| 50 | // pop k largest frequency items from the freqHeap |
| 51 | top := make([]int, k) |
| 52 | for i := 0; i < k; i++ { |
| 53 | top[i] = heap.Pop(h).(freqHeapVal).key |
| 54 | } |
| 55 | |
| 56 | return top |
| 57 | } |