[Golang][Leetcode][Stack & Queue]刷題系列-347-Top K Frequent Elements

2021-08-21 491 words 3 minutes

/leetcode347_stack_queue/golang_leetcode.png

Contents

347. Top K Frequent Elements

Level : Medium

原題連結 : Click

題目 :

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example :

Note

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]

Example 2:

Input: nums = [1], k = 1 Output: [1]

解題思路 :

題目需要我們把前k個出現最多數字回傳，光想這個需求大家可能會想到去做排序
這裡我提供兩個做法
1. Priority Queue 的作法
2. Bucket Sort 的作法
Priority Queue就是Heap sort的應用，這邊要用的是min-Heap，且會用到Insert與Heapify的操作，也需要自己實做出來，但基本的概念還是不困難的，主要就是將value-frequence裝進map裡，自定義一個Min-Heap，要實作heap sort，結構需是一種completed tree，每一個node需要放進value跟frequence，最重要的一點是需要在Insert與heapify操作裡限制tree的大小，因為我們最後答案只需要k個，在Insert中主要分成兩個區塊一個是k大小的tree尚未被填滿時與填滿後，未被填滿前都是直接加入並放入屬於它的位置(滿足Min-heap，比較的key為frequence)，若已填滿則看他是否frequence是否大於當前min-heap的head也就是目前最小的frequence來決定是否取代他，若有取代，並接著對他做heapify使得他前往她該在的位置。
Bucket Sort就較為容易了，他於counting sort跟radix sort一樣是以區段分類並非comparing sort，優點是best case可以做到O(n)，缺點是必須事先知道資料範圍才方便使用，在這個問題bucket sort就非常好用了，我們可以也先將value-frequence裝進map裡，宣告一個2D的slice，第一層我們是以frequence做為index，那大家會問那要宣告多大呢? frequence最大會到多大呢? 必定不會超過題目提供array的長度，所以我們就宣告其長度為len(nums)+1就好(因為Index是0開頭所以+1)，再將不同數字依照他們的frequence放進不同的箱子裡，但妙就妙在因為frequence早就排好了，所以在分類時就直接也為他們做好了排序，之後就直接由大frequence的箱子一個一個倒出來，略過空的箱子，然後只取前k個，就完成了!!

Priority Queue 的解法

time complexity: O(nlog(n)) , space complexity: O(n)

Runtime: 12 ms, faster than 84.67% of Go online submissions for Top K Frequent Elements.

 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

func topKFrequent(nums []int, k int) []int {
    
    freqMap := map[int]int{}
    
    priorityQ := &minHeap{
        nodes : make([]*Node, 0, k),
    }
    
    res := make([]int,0)
    
    for i := 0; i < len(nums); i++ {
        freqMap[nums[i]]++
    }
    
    for i, v := range freqMap {
        
        node := &Node{
            freq : v,
            val : i,
        }
        
        priorityQ.Insert(node)
    }
    
    for _, node := range priorityQ.nodes {
        res = append(res, (*node).val)
    }
    return res
}

type Node struct {
    freq int
    val int
}

type minHeap struct {
    nodes []*Node
}

func (this *minHeap) Insert(node *Node) {
    
    if cap(this.nodes) > len(this.nodes)  {
        this.nodes = append(this.nodes,node)
        
        i := len(this.nodes)-1
        for this.nodes[(i-1)/2].freq > this.nodes[i].freq {
            this.nodes[i] = this.nodes[(i-1)/2]
            i = (i-1)/2
            this.nodes[i] = node     
        }
        
    }else {
        
        if (*node).freq > this.nodes[0].freq {
            this.nodes[0] = node
            this.Heapify()   
        }
    }
}

func (this *minHeap) Heapify() {
    
    i := 0
    
    min := i
    
    for len(this.nodes)-1 > i*2 {
        
        if len(this.nodes) > i*2+1 && this.nodes[i*2+1].freq < this.nodes[min].freq {
            min = i*2+1
        }
        
        if len(this.nodes) > i*2+2 && this.nodes[i*2+2].freq < this.nodes[min].freq {
            min = i*2+2
        }
        
        if min == i {
            return
        }
        
        this.nodes[i], this.nodes[min] = this.nodes[min], this.nodes[i]
        i = min
    }
}

Bucket Sort 的解法

time complexity: O(n), space complexity: O(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

func topKFrequent(nums []int, k int) []int {
    
    freqMap := make(map[int]int,0)
    
    bucket := make([][]int, len(nums)+1)
    
    res := make([]int,0)
    
    for _, val := range nums {
        freqMap[val]++
    }
    
    for val, freq := range freqMap {
        bucket[freq] = append(bucket[freq], val)
    }
    
    for i := len(bucket)-1; i > 0 ; i-- {
        if len(bucket[i]) != 0 {
            res = append(res, bucket[i]...)
        }
    }
    
    return res[:k]  
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!