给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
type number struct {
number int
ncount int
}
// An IntHeap is a min-heap of ints.
type IntHeap []number
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i].ncount < h[j].ncount }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
// Push ...
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(number))
}
// Pop ...
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func topKFrequent(nums []int, k int) []int {
numberMap := make(map[int]int, 0)
for i := 0; i < len(nums); i++ {
if _, exist := numberMap[nums[i]]; !exist {
numberMap[nums[i]] = 1
continue
}
numberMap[nums[i]]++
}
h := new(IntHeap)
for n, count := range numberMap {
heap.Push(h, number{number: n, ncount: count})
if h.Len() > k {
heap.Pop(h)
}
}
numss := make([]int, 0)
for i := 0; i < h.Len(); i++ {
numss = append(numss, (*h)[i].number)
}
return numss
}
