給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素割卖。
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]
說明：
你可以假設(shè)給定的 k 總是合理的唱凯，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個數(shù)湿痢。
你的算法的時間復(fù)雜度必須優(yōu)于 O(n log n) , n 是數(shù)組的大小慕爬。
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
}
