leetcode(力扣) 347. 前 K 个高频元素（优先队列 & 堆 & 哈希计数器）

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

思路分析

法一( 哈希计数)：

可以用python里的Counter计数器统计出来所有的元素的出现频率，然后用most_common()方法取出排行前k个的元素。

关于most_common()，这里面的参数就是取前N大的数值，比如有

• nums = [1,1,1,2,2,3,5,5,5,5]，
• Counter之后，{5: 4, 1: 3, 2: 2, 3: 1}，
• 使用most_common(2)之后[[(5, 4), (1, 3)]]。
• 若k=2.显然返回的是[5,1]

法二（堆）：

python里的堆使用heapq包实现，默认为小根堆，如果要用大根堆，就让元素乘以负一。

堆的思路就是维护一个K字节大小的堆，堆类似于一个二叉树，每个树节点存的是一个元组(出现次数，元素值)，pop弹出从根节点弹出，push添加从叶子节点添加。

堆里比较的是出现次数，也就是按照出现次数进行排序。若所维护的堆长度小于k则往里push元素，若大于k则pop。

整体步骤：

• 首先遍历原数组，建立哈希表， key为元素，val为出现次数。
• 建立小根堆，遍历哈希表，将(出现次数，元素值）加入堆。
• 若堆大于K个，则pop弹出元素，否则就一直往里加。
• 倒叙输出小根堆。

这里有必要说一下为啥求最高频率用小根堆，而不是大根堆，可以想象一下，加入小根堆的元素，如果很小，则被pop掉了，所以所维护的小根堆最后剩下的就是最大的那k个元素，root为k个元素中最小的元素（出现频率最小的），最后输出的时候倒数输出这个堆，得到的就是前K个最大频率元素。

另外大顶堆 小顶堆 比较适合求前K个高频或者低频元素 大根堆求小的，小根堆求大的。时间复杂度：快排是nlogn 堆就是nlogk。

完整代码

法一：
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        hs = Counter(nums)
        res = []
        for i in hs.most_common():
            res.append(i[0])
        print(res[:k])
        return  res[:k]
法二：
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        import heapq
        hs = {}
        for i in range(len(nums)):
            if nums[i] in hs:
                hs[nums[i]] +=1
            else:
                hs[nums[i]] = 0
        
        min_heapq = []

        for key,val in hs.items():
            heapq.heappush(min_heapq,(val,key))
            if len(min_heapq) > k:
                heapq.heappop(min_heapq)
        res = [0] * k
        
        for i in  range(k-1,-1,-1):
            res[i] = heapq.heappop(min_heapq)[1]
        return res



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35