347.Top_K_Frequent_Elements.md

347. Top K Frequent Elements

First is record each element frequent, must to traverse all element, store this number and frequency in a map, Time complexity is O(n).

Then we have two solution:

1. Using sorting find top k element, time complexity is O(nlogn).
2. Max heap or Min heap to find k element, time complexity is O(nlogk). reference

So if you use a heap to deal with how to find k elements, k is only k = n in the worst case. The second method will be faster.

Solution 2 uses minheap, so when traversing the hash, elements are pushed into minheap. If the size of minheap exceeds k, the root node is popped, which is equivalent to maintaining a high-frequency element with a size of k. Finally, taking out the elements in the heap is the answer

Solution 1

func topKFrequent(nums []int, k int) []int {
	var result []int
	hash := map[int]int{}
	for _, num := range nums {
		hash[num]++
	}

	for key := range hash {
		result = append(result, key)
	}

	sort.Slice(result, func(i, j int) bool {
		return hash[result[i]] > hash[result[j]]
	})
	return result[:k]
}

Solution 2

func topKFrequent(nums []int, k int) []int {
	var result []int
	hash := map[int]int{}
	for _, num := range nums {
		hash[num]++
	}
	h := &MinHeap{}
	heap.Init(h)
	for key, value := range hash {
		heap.Push(h, HeapNode{num: key, frequent: value})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	for i := len(*h) - 1; i >= 0; i-- {
		result = append(result, (*h)[i].num)
	}
	return result
}

type MinHeap []HeapNode

type HeapNode struct {
	num      int
	frequent int
}

func (heap MinHeap) Len() int {
	return len(heap)
}

func (heap MinHeap) Less(i, j int) bool {
	return heap[i].frequent < heap[j].frequent
}

func (heap MinHeap) Swap(i, j int) {
	heap[i], heap[j] = heap[j], heap[i]
}

func (heap *MinHeap) Push(x interface{}) {
	*heap = append(*heap, x.(HeapNode))
}

func (heap *MinHeap) Pop() interface{} {
	len := len(*heap)
	x := (*heap)[len-1]
	*heap = (*heap)[:len-1]
	return x
}