leetcode347 前 K 个高频元素

题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

解析

听名字是个top K问题，首先也得记住，top K问题一般考虑用堆解决，其中求前K大元素用小顶堆，求前K小用大顶堆，原因是这个二叉树中，push到叶子节点，而pop的是根节点（最小值或最大值）。
然后这个的时间复杂度是O(nlogk)，而直接快排的时间复杂度是O(nlogn)，所以数据量越大，差别越明显（感觉数据量小的时候可能差别还好）。
另外一个就是golang中调用堆的方式：
使用方法

func topKFrequent(nums []int, k int) []int {
	//用一个map记录每个元素出现的次数
	map_num := map[int]int{}
	for _, item := range nums {
		map_num[item]++
	}
	h := &IHeap{}
	heap.Init(h)
	//所有元素入堆，堆的长度为k
	for key, value := range map_num {
		heap.Push(h, [2]int{key, value})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	res := make([]int, k)
	//按顺序返回堆中的元素
	for i := 0; i < k; i++ {
		res[k-i-1] = heap.Pop(h).([2]int)[0]
	}
	return res

}

//构建一个小顶堆，注意求前K大值用小顶堆，求前K小值用大顶堆，原因可以看堆的原理
//下面都是构建堆的过程，因为GO中没有堆，得自己建一个
type IHeap [][2]int

func (h IHeap) Len() int {
	return len(h)
}

func (h IHeap) Less(i, j int) bool {
	return h[i][1] < h[j][1]
}

func (h IHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}

func (h *IHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51