347. 前 K 个高频元素

用时:30min

思路是先用On 的时间复杂度去计数, 然后用最小堆的方式求解

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Heap {
constructor(list, compare = (a, b) => a - b) {
this.left = index => 2 * index + 1
this.right = index => 2 * index + 2
this.parent = index => Math.floor((index - 1) / 2)
this.heapify = (index = 0) => {
const { list } = this
const leftIndex = this.left(index)
const rightIndex = this.right(index)
let maxIndex = index
if (list[leftIndex] !== undefined
&& this.compare(list[maxIndex], list[leftIndex]) > 0) {
maxIndex = leftIndex
}
if (list[rightIndex] !== undefined
&& this.compare(list[maxIndex], list[rightIndex]) > 0) {
maxIndex = rightIndex
}
if (index !== maxIndex) {
const temp = list[index]
list[index] = list[maxIndex]
list[maxIndex] = temp
this.heapify(maxIndex)
}
}
this.buildHeap = () => {
for (let i = Math.floor(this.list.length / 2); i >= 0; i--) {
this.heapify(i)
}
return this.list
}
this.extract = () => {
const temp = this.list[0]
this.list[0] = this.list[this.list.length - 1]
this.list[this.list.length - 1] = temp
const result = this.list.pop()
this.heapify(0)
return result
}
this.top = () => {
return this.list[0]
}
this.insert = (item) => {
const { list } = this
list.push(item)
let index = list.length - 1
let parentIndex = this.parent(index)
while (list[parentIndex] !== undefined && this.compare(list[parentIndex], list[index]) > 0) {
const temp = list[index]
list[index] = list[parentIndex]
list[parentIndex] = temp
index = parentIndex
parentIndex = this.parent(index)
}
}
this.list = list
this.compare = compare
this.buildHeap()
}
}

var topKFrequent = function(nums, k) {
var map = {}
for(let i = 0 ; i < nums.length ; i ++) {
var num = nums[i]
if (map[num] == undefined) {
map[num] = 1
} else {
map[num] ++
}
}
// 使用最小堆 ,维护 K 个最高的元素
var heap = new Heap([],(a,b) => a[1] - b[1])
var K = 0
// 因为api是最大堆,所以要取相反数
Object.entries(map).forEach(([key,val]) => {
if (K < k) {
heap.insert([key,-val])
} else {
var top = heap.top()
if (val > - top[1]) {
heap.extract()
heap.insert([key,-val])
}
}
})
return heap.list.map((v) => v[0]).slice(0,k)
};