Top K Frequent Elements

Solution1

use bucket sort

time complexity :O(n)

1. 製作 num_count 字典，將每個數字放進字典中，key 為數字 value 為出現次數

2. 用 bucket sort
   list index 為出現次數，資料為 list，放出現該次數的數字們
   圖中範例，1 出現 3 次，所以放在 index 3 的 list 中；2 出現 2 次，所以放在 index 2 的 list 中

   
3. 創建 answer list，將 bucket 由後往前，取出 k 個最大值，方法是 answer list 的長度等於 k 時，就可以 return answer 了

class Solution:

def topKFrequent(self, nums: List[int], k: int) -> List[int]:

# 1.

num_count = dict()

for num in nums:

num_map[num] = num_map.get(num, 0) + 1

# 2. bucket sort

bucket = [[] for i in range(len(nums))]

for key, value in num_map.items():

bucket[value - 1].append(key)

# 3.

ans = list()

for i in range(len(nums) - 1, -1, -1):

if bucket[i]:

ans.extend(bucket[i])

if len(ans) == k:

return ans

Solution2

use heap max

time complexity: O(klogn)

k層（取 k 個最大值，每一層花費時間 logn）

Video Solution