347.前 k 个高频元素

题目描述

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

示例 1:

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

示例 2:

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

提示：

1 <= nums.length <= 10⁵
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(nlogn) ，其中 n 是数组大小。

解法一：哈希表 + 优先队列

 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


var record map[int]int

type PriorityQueue struct {
    sort.IntSlice
}

func (pq *PriorityQueue) Less(i, j int) bool {
    // 注意：优先队列里存储的是 key，所以比较时要取对应的 value 来进行比较。
    return record[pq.IntSlice[i]] < record[pq.IntSlice[j]]
}

func (pq *PriorityQueue) Push(val interface{}) {
    pq.IntSlice = append(pq.IntSlice, val.(int))
}

func (pq *PriorityQueue) Pop() interface{} {
    tmp := pq.IntSlice
    ret := tmp[len(tmp)-1]
    pq.IntSlice = tmp[:len(tmp)-1]
    return ret
}

func topKFrequent(nums []int, k int) []int {
    record = make(map[int]int)
    for _, num := range nums {
        record[num]++
    }
    pq := &PriorityQueue{make([]int, 0, k)}
    // 注意不要将变量 key 命名为变量 k，因为变量 k 已存在，会导致覆盖。
    for key, v := range record {
        if len(pq.IntSlice) < k {
            heap.Push(pq, key)
        } else {
            if record[pq.IntSlice[0]] < v {
                heap.Pop(pq)
                heap.Push(pq, key)
            }
        }
    }
    return pq.IntSlice
}