Top K Frequent Elements

1. Problem Description

Given a non-empty integer array, return the k most frequent elements.

2. Approach

1. Approach 1
   • Use a map to count frequencies
   • Then sort by frequency
2. Approach 2
   • Use a map to count frequencies
   • Min-heap

3. Implementation

3.1. map

func topKFrequent(nums []int, k int) []int {
    m := make(map[int]int, 0)
    for _, num := range nums {
        m[num] += 1
    }
    lst := make([]int, 0, len(m))
    for k,_ := range m {
        lst = append(lst, k)
    }
    sort.Slice(lst , func(i, j int) bool {
        return m[lst[i]] > m[lst[j]]
    })
    return lst[:k]
}

3.2. Min-Heap

type item struct {
	num   int
	count int
}

type itemHeap struct {
	items []*item
}

func (h *itemHeap) Len() int {
	return len(h.items)
}

func (h *itemHeap) Less(i, j int) bool {
	return h.items[i].count < h.items[j].count
}

func (h *itemHeap) Swap(i, j int) {
	h.items[i], h.items[j] = h.items[j], h.items[i]
}

func (h *itemHeap) Push(x interface{}) {
	h.items = append(h.items, x.(*item))
}

func (h *itemHeap) Pop() interface{} {
	num := h.items[len(h.items)-1]
	h.items = h.items[:len(h.items)-1]
	return num
}

func topKFrequent(nums []int, k int) []int {
	m := make(map[int]int, 0)
	for _, num := range nums {
		m[num]++
	}

	h := &itemHeap{}
	for num, count := range m {
		if h.Len() < k {
			heap.Push(h, &item{
				num:   num,
				count: count,
			})
		} else {
			top := h.items[0]
			if top.count < count {
				heap.Pop(h)
				heap.Push(h, &item{
					num:   num,
					count: count,
				})
			}
		}
	}

	res := make([]int, 0, k)
	for i := 0; i < k; i++ {
		res = append(res, heap.Pop(h).(*item).num)
	}
	return res
}

4. References

• 347. Top K Frequent Elements - Top K Frequent Elements - LeetCode