347.前K个高频元素
347.前K个高频元素
题解
题目：给一个数组，统计出现频率前k高的元素
思路：
1. 将元素和出现次数存入map 2. 快排出现次数
1.堆排序，小根堆 2.当堆中的元素大于k时，弹出堆顶，因为是小根堆，所有弹出的都是最小的出现次数 3.那么剩余堆中的k个元素就是出现频率前k高的元素了
注意Pop，我之前一直以为Pop是弹出末尾的元素，类似队列，结果Pop是弹出堆顶元素，并维护堆，那么对于小根堆来说，Pop就是弹出最小的元素
func Pop(h Interface) interface{} { n := h.Len() - 1 h.Swap(0, n) down(h, 0, n) return h.Pop() }
代码
func topKFrequent(nums []int, k int) []int { mp := make(map[int]int) for _, v := range nums { mp[v]++ } var arr [][2]int for k, v := range mp { arr = append(arr, [2]int{k, v}) } sort.Slice(arr, func(i, j int) bool { return arr[i][1] > arr[j][1] }) ans := make([]int, 0) for i := 0; i < k; i++ { ans = append(ans, arr[i][0]) } return ans }
func topKFrequent(nums []int, k int) []int { mp := make(map[int]int) for _, v := range nums { mp[v]++ } h := new(myHeap) heap.Init(h) for key, val := range mp { heap.Push(h, [2]int{key, val}) if h.Len() > k { heap.Pop(h) //删除最小元素 } } ans := make([]int, k) for i := 0; i < k; i++ { ans[i] = heap.Pop(h).([2]int)[0] } return ans } type myHeap [][2]int func (h myHeap) Len() int { return len(h) } func (h myHeap) Less(i, j int) bool { return h[i][1] < h[j][1] } func (h myHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *myHeap) Push(x interface{}) { *h = append(*h, x.([2]int)) } func (h *myHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x }
