<commit_before>/* https://leetcode.com/problems/top-k-frequent-elements/
Given a non-empty array of integers, return the k most frequent elements.

Example 1:

	Input: nums = [1,1,1,2,2,3], k = 2
	Output: [1,2]

Example 2:

	Input: nums = [1], k = 1
	Output: [1]

Note:

	You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
	Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
*/

package larray

import (
	"sort"
)

type matrixSlice [][2]int

func (m matrixSlice) Len() int {
	return len(m)
}
func (m matrixSlice) Less(i, j int) bool {
	return m[i][1] > m[j][1]
}

func (m matrixSlice) Swap(i, j int) {
	m[i], m[j] = m[j], m[i]
}

func topKFrequent(nums []int, k int) []int {
	countMaps := map[int]int{}

	for _, num := range nums {
		countMaps[num]++
	}

	ms := make(matrixSlice, len(countMaps))
	idx := 0
	for k, v := range countMaps {
		ms[idx] = [2]int{k, v}
		idx++
	}

	sort.Sort(ms)

	res := make([]int, k)
	for i := 0; i < k; i++ {
		res[i] = ms[i][0]
	}
	return res
}<commit_msg>347. Top K Frequent Elements: use heap<commit_after>/* https://leetcode.com/problems/top-k-frequent-elements/
Given a non-empty array of integers, return the k most frequent elements.

Example 1:

	Input: nums = [1,1,1,2,2,3], k = 2
	Output: [1,2]

Example 2:

	Input: nums = [1], k = 1
	Output: [1]

Note:

	You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
	Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
*/

package larray

import (
	"container/heap"
)

// An IntHeap is a min-heap of ints.
type IntHeap [][2]int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i][1] > h[j][1] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

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.([2]int))
}

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 {
	countMaps := map[int]int{}

	for _, num := range nums {
		countMaps[num]++
	}

	h := &IntHeap{}
	heap.Init(h)
	for k, v := range countMaps {
		heap.Push(h, [2]int{k, v})
	}

	res := make([]int, k)
	for i := 0; i < k; i++ {
		val := heap.Pop(h).([2]int)
		res[i] = val[0]
	}
	return res
}
{'fraction_non_alphanumeric': 0.17459016393442622, 'fraction_numerical': 0.020901639344262295, 'mean_word_length': 3.2824561403508774, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7564184', 'n_tokens_mistral': 1069, 'n_tokens_neox': 1015, 'n_words': 331}