題目鏈接
難度：中等 ??????類型：
給定一個(gè)非空的整數(shù)數(shù)組商源，返回其中出現(xiàn)頻率前 k 高的元素留夜。
說(shuō)明：
你可以假設(shè)給定的 k 總是合理的真椿，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個(gè)數(shù)娜遵。
你的算法的時(shí)間復(fù)雜度必須優(yōu)于 O(n log n) , n 是數(shù)組的大小丽声。
示例1
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例2
輸入: nums = [1], k = 1
輸出: [1]
解題思路
- 用collections的Counter來(lái)統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)
- 構(gòu)建k個(gè)節(jié)點(diǎn)的最小堆礁蔗，以元素出現(xiàn)的頻率作為比較依據(jù)。
遍歷所有元素雁社，規(guī)則如下：
- 若堆未滿浴井，元素入堆
- 若堆滿了，且當(dāng)前元素的頻率大于堆頂元素的頻率霉撵，堆頂元素出堆磺浙，該元素入堆洪囤。
- 若堆滿了，當(dāng)前元素的頻率小于堆頂元素撕氧，不管它
元素入堆的時(shí)間復(fù)雜度為O(log k)
使用heapq庫(kù)中的 nlargest瘤缩，可以在相同時(shí)間內(nèi)完成，但只需要一行代碼解決伦泥。
代碼實(shí)現(xiàn)
方法1：
class Solution:
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
count = collections.Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
方法2：
import collections
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
counter = collections.Counter(nums)
most = counter.most_common(k)
return [x[0] for x in most]
