Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
解法
key: 数値の出現回数, value: 数値のmapを作り、key, valueが逆転したmapを作った上でkeyを降順ソートし、k要素分だけ返すようにする
時間計算量 O(NlogN) , N=len(nums)
mapを作成するのにN回ループを回した上で、numsをsortしている
空間計算量 O(N)
code:main.go
func topKFrequent(nums []int, k int) []int {
// key: num, value: freq
for _, num := range nums {
}
// key: freq, value: num
reversedM := make(mapint[]int) for num, freq := range m {
reversedMfreq = append(reversedMfreq, num) }
freqs := make([]int, 0, len(reversedM))
for f := range reversedM {
freqs = append(freqs, f)
}
sort.Slice(freqs, func(i, j int) bool {
})
ret := make([]int, 0, k)
for _, f := range freqs {
for _, num := range reversedMf { ret = append(ret, num)
if len(ret) == k {
return ret
}
}
}
return ret
}
Heapでの解法。
code:heap.go
type Element struct {
val int
freq int
}
type MinHeap []Element
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return hi.freq < hj.freq } func (h MinHeap) Swap(i, j int) { hi, hj = hj, hi } func (h *MinHeap) Push(x any) {
*h = append(*h, x.(Element))
}
func (h *MinHeap) Pop() any {
old := *h
n := len(old)
return ret
}
func topKFrequent(nums []int, k int) []int {
freqMap := make(mapintint) for _, val := range nums {
}
h := &MinHeap{}
heap.Init(h)
for val, freq := range freqMap {
heap.Push(h, Element{val, freq})
if h.Len() > k {
heap.Pop(h)
}
}
res := make([]int, 0, k)
for _, e := range *h {
res = append(res, e.val)
}
return res
}