347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/

solution

• 直接法

import collections

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        res = dict(collections.Counter(nums))  
        res = sorted(res.items(), key=lambda x: x[1], reverse=True)
        return [i[0] for i in res[-k:]]

时间复杂度：O() 空间复杂度：O()

• 堆

  • 优化点在于选出最大的k个，不需要对全部排序。只需要前k排序。优先队列/堆

  • 堆解决top k问题时，最后pop消耗空间较大，迭代过程中超过k立即pop优化空间

import collections
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq_dict = collections.defaultdict(int)
        for num in nums:
            freq_dict[num] += 1
        
        heap = []
        for num, freq in freq_dict.items():  # heap如果最小堆中按第一个元素升序顺序排
            heapq.heappush(heap, (-freq, num))
        
        res = []
        for _ in range(k):
            res.append(heapq.heappop(heap)[1])
        return res

时间复杂度：O() 空间复杂度：O()

• 桶排序 bucket sort

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        bucket = [[] for _ in range(len(nums)+1)]
        res = []
        freq = collections.Counter(nums)
        
        for key, val in freq.items():  # key为数字，val为这个数字出现的次数
            bucket[val].append(key)  # 值是出现次数，key是num. 填充桶时，次数最多的越往大的桶放
        
        for i in range(len(bucket)-1, -1, -1):  # 从次数大的桶里往回，每个桶本身是key
            res += bucket[i]
            if len(res) == k:
                return res

时间复杂度：O(n) 空间复杂度：O(n)

follow up

• 大数据的Top K frequent