題目出處
難度
medium
個人範例程式碼
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if not nums:
return nums
# O(N)
counter = Counter(nums)
freq_counter = defaultdict(list)
# O(N)
for key, value in counter.items():
freq_counter[value].append(key)
ans = []
# O(NlogN)
for key in sorted(freq_counter.keys(), reverse=True):
ans += freq_counter[key]
k -= len(freq_counter[key])
if k <= 0:
break
return ans
直接使用 dict.items() + sorted tuple 排序
更俐落一點的寫法，直接把 dict.items() 轉作 tuple 來看後，直接排序
如果用法不熟，用上面方法即可。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if not nums:
return nums
# O(N)
counter = Counter(nums) # key: freq
# O(NlogN)
sorted_tuple_by_freq = sorted(counter.items(), key=lambda x: x[1], reverse=True)
# print(sorted_tuple_by_freq)
ans = []
for i in range(k):
ans.append(sorted_tuple_by_freq[i][0])
return ans
算法說明
我們先計算數字頻率，可以搭配內建函數 counter 快速實現，
再來針對出現次數進行排序，
然後選出前 K 個答案即可。
input handling
如果沒有 nums，return nums
Boundary conditions
用 for 來控制範圍