【Leetcode刷题】：Python：347. 前 K 个高频元素_python 出现频率前k个的元素

题目

347. 前 K 个高频元素

代码：hash+堆排序

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:   
        # 构造hash
        dic = {}
        for i in nums:
            dic[i] = dic.get(i, 0)+1
        self.res = []
        for i in dic:
            self.res.append([dic[i], i])
        # 构造大顶堆
        for i in range(len(self.res)//2, -1, -1):
            self.max_heap(i, len(self.res))
        # 堆排序
        ans = []
        for j in range(len(self.res)-1, len(self.res)-k-1, -1):
            ans.append(self.res[0][1])
            self.res[0], self.res[j] = self.res[j], self.res[0]
            self.max_heap(0, j)
        return ans 

    def max_heap(self, i, n):
        j = i*2+1
        while j < n:
            if j+1 < n and self.res[j+1][0] > self.res[j][0]:
                j += 1
            if self.res[j][0] > self.res[i][0]:
                self.res[j], self.res[i] = self.res[i], self.res[j]
                i = j 
                j = i*2+1 
            else:
                break

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