当前位置:   article > 正文

【Leetcode刷题】:Python:347. 前 K 个高频元素_python 出现频率前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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/72837
推荐阅读
相关标签
  

闽ICP备14008679号