-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
131 lines (107 loc) · 2.52 KB
/
main.go
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package topkfrequentelements
import (
"container/heap"
"sort"
)
// 方法一: 使用 PriorityQueue
// 時間複雜 O(Nlogk), 空間複雜 O(N)
// 首先遍歷整個數組,並使用哈希表記錄每個數字出現的次數,並形成一個「出現次數數組」
// 建立一個 PriortyQueue, 將「出現次數數組」丟進去
// 在把 PriortyQueue pop的值丟到 result
func TopKFrequent(nums []int, k int) []int {
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
q := PriorityQueue{}
for key, count := range m {
item := &Item{key: key, count: count}
q.PushPQ(item)
}
var result []int
for len(result) < k {
item := q.PopPQ()
result = append(result, item.key)
}
return result
}
// Item define
type Item struct {
key int
count int
}
/*
// A PriorityQueue implements heap.Interface and holds Items.
package heap
import "sort"
type Interface interface {
sort.Interface
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}
*/
type PriorityQueue []*Item
/*
// An implementation of Interface can be sorted by the routines in this package.
// The methods refer to elements of the underlying collection by integer index.
type Interface interface {
// Len is the number of elements in the collection.
Len() int
Less(i, j int) bool
Swap(i, j int)
}
*/
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
// 大到小排序
return pq[i].count > pq[j].count
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pg *PriorityQueue) Push(v interface{}) {
item := v.(*Item)
*pg = append(*pg, item)
}
func (pg *PriorityQueue) Pop() interface{} {
n := len(*pg)
item := (*pg)[n-1]
*pg = (*pg)[:n-1]
return item
}
func (pg *PriorityQueue) PushPQ(v *Item) {
heap.Push(pg, v)
}
func (pg *PriorityQueue) PopPQ() *Item {
return heap.Pop(pg).(*Item)
}
// 方法二: 使用 Quick Sort
// 時間複雜 O(), 空間複雜 O()
func TopKFrequentQuickSort(nums []int, k int) []int {
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
m[nums[i]]++
}
values := [][]int{}
for key, count := range m {
values = append(values, []int{key, count})
}
result := []int{}
sort.Sort(sortValue(values))
for i := 0; i < k; i++ {
result = append(result, values[i][0])
}
return result
}
type sortValue [][]int
func (s sortValue) Len() int {
return len(s)
}
func (s sortValue) Less(i, j int) bool {
return s[i][1] > s[j][1]
}
func (s sortValue) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}