未分類

Top K Frequent Elements

Go, HashTable, Heap, LeetCode

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example:

1
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
提示 解題應用
HashTable HashMap

Default:

1
2
3
func topKFrequent(nums []int, k int) []int {
}

解答思路:

這題我的做法很單純，就是先利用hashmap來統計各個數字所出現的次數之後，再對hashmap統計的次數做排序，當然最糟的情況(也就是所有元素都沒有重覆)時間複雜度會是O(nlogn)，除此之外都小於O(nlogn)，也許依討論上較有效率的解法是用上heap會更好，但目前就暫時先做保留。

程式碼解說:

由於hashmap並沒有辦法直接做排序，因此這邊的做法是將hashmap的統計結果搬至自行定義的結構陣列之後再做排序

1
2
3
4
5
6
7
8
type Pair struct {
	Num    int
	Amount int
}
type PairList []Pair
func (p PairList) Len() int           { return len(p) }
func (p PairList) Less(i, j int) bool { return p[i].Amount < p[j].Amount }
func (p PairList) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

而實際做法正如思路所述，先利用hashmap來統計各個數字所出現的次數之後，再將hashmap的統計搬至自行定義的結構陣列做排序(由大排至小)，最後只要從結構陣列開頭開始取出k個數字放至結果陣列之中便能向上做回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func topKFrequent(nums []int, k int) []int {
	var i int
	var result []int
	hashMap := make(map[int]int)
	for _, v := range nums {
		hashMap[v]++
	}
	pl := make(PairList, len(hashMap))
	for k, v := range hashMap {
		pl[i] = Pair{k, v}
		i++
	}
	sort.Sort(sort.Reverse(pl))
	for j := 0; j < k; j++ {
		result = append(result, pl[j].Num)
	}
	return result
}

完整程式碼:

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
type Pair struct {
	Num    int
	Amount int
}
type PairList []Pair
func (p PairList) Len() int           { return len(p) }
func (p PairList) Less(i, j int) bool { return p[i].Amount < p[j].Amount }
func (p PairList) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func topKFrequent(nums []int, k int) []int {
	var i int
	var result []int
	hashMap := make(map[int]int)
	for _, v := range nums {
		hashMap[v]++
	}
	pl := make(PairList, len(hashMap))
	for k, v := range hashMap {
		pl[i] = Pair{k, v}
		i++
	}
	sort.Sort(sort.Reverse(pl))
	for j := 0; j < k; j++ {
		result = append(result, pl[j].Num)
	}
	return result
}

總結:

這題我的做法很單純，就是先利用hashmap來統計各個數字所出現的次數之後，再對hashmap統計的次數做排序，當然最糟的情況(也就是所有元素都沒有重覆)時間複雜度會是O(nlogn)，除此之外都小於O(nlogn)，也許依討論上較有效率的解法是用上heap會更好，但目前就暫時先做保留。

分享到