Top K Elements 是我最喜歡的類型之一，因為它很好理解，通常要你在某個序列內找出前幾大、前幾小或者前幾頻率高的元素之類，都是屬於這類型的問題。
先來看一下這個問題原文長怎樣？
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
- 1 <= nums.length <=
kis in the range[1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
這個題目算是 The Top K Elements 系列的入門題了，要你抓出前K大頻率的元素，此時我們就可以在腦袋中想一下，如果要抓出前幾大，暴力解法是什麼？最簡單的就是塞進 Map 接著計算數量，最後走訪整個 Map 就可以知道前 K 個最高頻率的元素是哪些。
我們先定義 HashMap 是透過 Key 與 Value 來決定我們的元素值跟次數，因此，就會是以 Key 當作我們的元素值，而 Value 就是我們計算頻率的次數。
Pair<Int, Int>
這邊要來介紹一下一個資料結構 Heap，它是一個樹狀的資料結構，是一種完全二元樹，特性是 Root 永遠是最大或最小的元素，如果你宣告了一個以最小值為 Root 的 Heap，則稱之為 MinHeap，反之則為 MaxHeap。
知道這個資料結構的特性以後，我們做這一題就簡單許多，在Java裡面，如果你想要使用 Heap 這個資料結構，那就需要自己定義一個 PriorityQueue 來決定宣告 MinHeap 還是 MaxHeap，
我們這個題目就是需要抓出最高頻率的元素，因此，會採取一個 MaxHeap 幫我們完成這件事情。
怎麼宣告呢？在這邊我們需要
val maxHeap = PriorityQueue<Pair<Int, Int>>(){p1, p2->
p2.second - p1.second
}
透過這樣我們就大致上完成了我們的基本工具了，接著我們會先把所有元素倒入到我們宣告的HashMap，在這邊我們會順便用到一個函式 getOrDefault()，前面是取得當前的 key，如果沒有這個 key 則我們塞入一個預設的 value 給它，再對他進行加1，這樣做有什麼好處？答案是可以讓程式看起來更為精簡，不然你會需要多寫幾行來完成這樣的功能。
大概會像是這樣。
if(hashMap.contains(nums[i])){
var count = hashMap[nums[i]]?:0
count++
hashMap[nums[i]] = count
} else{
hashMap[nums[i]] = 1
}
但是如果是用這個方式就可以一行解決。
for(i in nums.indices){
hashMap[nums[i]] = hashMap.getOrDefault(nums[i], 0) + 1
}
最後我們會將 Map 的資料全部丟進 Heap，而Heap塞進去後就會進行排序。
hashMap.forEach{ key, value->
var pair = Pair<Int, Int>(key, value)
maxHeap.add(pair)
}
最後我們只需要根據題意，抓出前 K 個元素就代表著那是頻率最高的前 K 個元素了。
val result = IntArray(k)
for(i in 0..k-1){
val p = maxHeap.poll() ?: null
if(p != null){
result[i] = p.first
}
}
以下是完整程式碼。
class Solution {
fun topKFrequent(nums: IntArray, k: Int): IntArray {
val maxHeap = PriorityQueue<Pair<Int, Int>>(){p1, p2->
p2.second - p1.second
}
val hashMap = HashMap<Int, Int>()
for(i in nums.indices){
hashMap[nums[i]] = hashMap.getOrDefault(nums[i], 0) + 1
}
hashMap.forEach{ key, value->
var pair = Pair<Int, Int>(key, value)
maxHeap.add(pair)
}
val result = IntArray(k)
for(i in 0..k-1){
val p = maxHeap.poll() ?: null
if(p != null){
result[i] = p.first
}
}
return result
}
}
透過這樣的方法解決，就可以在 O(NLogN) 的時間下處理完畢。