堆

约 90 个字 20 行代码 预计阅读时间 1 分钟 总阅读量 次

347. 前K个高频元素

🔑🔑 难度：Medium 中等

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

示例 1:

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

输出: [1,2]

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        record = defaultdict(int)
        # heappush
        # heapppushpop
        for num in nums:
            record[num] += 1

        array = []
        for val, cnt in record.items():
            if len(array) < k:
                heapq.heappush(array, (cnt, val))
            elif  cnt > array[0][0]:
                heapq.heappushpop(array, (cnt, val))

        result = []
        for val in array:
            result.append(val[1])
        return result

维护一个固定大小的大顶堆即可。

---