題目鏈接
難度：中等 ??????類型：

給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。

說明：

你可以假設(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]

解題思路

1. 用collections的Counter來統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)
2. 構(gòu)建k個(gè)節(jié)點(diǎn)的最小堆，以元素出現(xiàn)的頻率作為比較依據(jù)。
   遍歷所有元素，規(guī)則如下：

• 若堆未滿，元素入堆
• 若堆滿了，且當(dāng)前元素的頻率大于堆頂元素的頻率，堆頂元素出堆，該元素入堆。
• 若堆滿了，當(dāng)前元素的頻率小于堆頂元素，不管它
  元素入堆的時(shí)間復(fù)雜度為O(log k)

使用heapq庫中的 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]

本文鏈接：http://www.itdecent.cn/p/e6774156e902