一、问题描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

二、方案一：哈希表 + 快速选择

1、思路

• 使用哈希表统计每个元素出现的频率。
• 将哈希表中的键值对转换成数组，每个元素是一个长度为2的数组，第一个元素是数值，第二个元素是频率。
• 使用快速选择算法（类似于快速排序）找到第 k 大的频率值。
• 遍历哈希表，将频率大于等于第 k 大频率的元素加入到结果中。

2、代码实现

func topKFrequent(nums []int, k int) []int {
	occurrences := map[int]int{}
	// 获取每个数字出现次数
	for _, num := range nums {
		occurrences[num]++
	}
	values := [][]int{}
	for key, value := range occurrences {
		values = append(values, []int{key, value})
	}
	ret := make([]int, k)
	qsort(values, 0, len(values)-1, ret, 0, k)
	return ret
}

func qsort(values [][]int, start, end int, ret []int, retIndex, k int) {
	rand.Seed(time.Now().UnixNano())
	picked := rand.Int()%(end-start+1) + start
	values[picked], values[start] = values[start], values[picked]

	pivot := values[start][1]
	index := start

	for i := start + 1; i <= end; i++ {
		// 使用双指针把不小于基准值的元素放到左边，
		// 小于基准值的元素放到右边
		if values[i][1] >= pivot {
			values[index+1], values[i] = values[i], values[index+1]
			index++
		}
	}
	values[start], values[index] = values[index], values[start]
	if k <= index-start {
		// 前 k 大的值在左侧的子数组里
		qsort(values, start, index-1, ret, retIndex, k)
	} else {
		// 前 k 大的值等于左侧的子数组全部元素
		// 加上右侧子数组中前 k - (index - start + 1) 大的值
		for i := start; i <= index; i++ {
			ret[retIndex] = values[i][0]
			retIndex++
		}
		if k > index-start+1 {
			qsort(values, index+1, end, ret, retIndex, k-(index-start+1))
		}
	}
}

3、复杂度分析

• 时间复杂度：平均情况下为 O(n)，最坏情况下为 O(n^2)。
• 空间复杂度：O(n)，用于存储哈希表和频率数组。

三、方案二：哈希表 + 最小堆

1、思路

• 使用哈希表统计每个元素出现的频率。
• 创建一个大小为 k 的最小堆，用于存储频率最高的 k 个元素。
• 遍历哈希表，如果当前元素的频率大于堆顶元素的频率，则替换堆顶元素。
• 最终堆中的元素即为出现频率前 k 高的元素。

2、代码实现

import "container/heap"
type IntFreq struct {
    Num   int
    Freq  int
}
type IntFreqHeap []IntFreq
func (h IntFreqHeap) Len() int           { return len(h) }
func (h IntFreqHeap) Less(i, j int) bool { return h[i].Freq < h[j].Freq }
func (h IntFreqHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntFreqHeap) Push(x interface{}) {
    *h = append(*h, x.(IntFreq))
}
func (h *IntFreqHeap) 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 {
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }
    h := &IntFreqHeap{}
    heap.Init(h)
    for num, freq := range freqMap {
        if h.Len() < k {
            heap.Push(h, IntFreq{Num: num, Freq: freq})
        } else if freq > h.Peek().(IntFreq).Freq {
            heap.Pop(h)
            heap.Push(h, IntFreq{Num: num, Freq: freq})
        }
    }
    result := make([]int, 0, k)
    for h.Len() > 0 {
        result = append(result, heap.Pop(h).(IntFreq).Num)
    }
    return result
}

3、复杂度分析

• 时间复杂度：O(nlogk)，其中 n 是数组的长度，logk 是堆操作的时间复杂度。
• 空间复杂度：O(n)，用于存储哈希表和最小堆。

四、总结

方案一使用快速选择算法，可以在平均情况下达到线性