【堆】——前K个高频元素

347. 前K个高频元素

题目难度：中等

相关标签：[此处可根据实际相关标签补充完整，如数组、哈希表、堆、排序等]

相关企业：[可补充涉及考察该知识点的相关企业]

题目描述

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

示例1

输入：nums = [1,1,1,2,2,3]，k = 2
输出：[1,2]

示例2

输入：nums = [1]，k = 1
输出：[1]

提示信息

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶要求

你所设计算法的时间复杂度必须优于 O(n log n)，其中 n 是数组大小。

解法一：粗暴排序法（虽然不满足题目时间复杂度要求，但先给出实现思路供参考）

from typing import List


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
        解法一：粗暴排序法

        思路：
        1. 首先使用字典统计每个元素在数组nums中出现的频次。
        2. 然后将字典中的键值对转换为包含元素及其频次的元组形式，并放入一个列表中。
        3. 接着对这个列表按照元素频次进行降序排序（频次高的在前）。
        4. 最后取排序后的列表中的前k个元素的元素部分（即去掉频次信息），作为前k个高频元素返回。

        参数：
        - nums: 输入的整数数组
        - k: 要获取的前k个高频元素的数量

        返回：
        返回一个列表，包含数组nums中出现频率前k高的元素
        """
        # 步骤一：统计每个元素的出现频次
        frequency_dict = {}
        for num in nums:
            if num in frequency_dict:
                frequency_dict[num] += 1
            else:
                frequency_dict[num] = 1

        # 步骤二：将字典转换为包含元素及其频次的元组列表
        frequency_list = [(num, frequency_dict[num]) for num in frequency_dict]

        # 步骤三：按照频次对元组列表进行降序排序
        frequency_list.sort(key=lambda x: x[1], reverse=True)

        # 步骤四：获取前k个高频元素
        result = [frequency_list[i][0] for i in range(k)]

        return result

解法二：最小堆

from typing import List
import heapq


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
        解法二：最小堆

        思路：
        1. 先通过字典统计数组nums中每个元素的出现频次。
        2. 创建一个最小堆，堆中的元素是包含元素及其频次的元组形式。
        3. 遍历统计频次的字典，对于每个元素：
            - 如果最小堆的大小小于k，直接将元素及其频次的元组加入堆中。
            - 如果最小堆的大小等于k，将当前元素的频次与堆顶元素（堆中频次最小的元素）的频次进行比较：
                - 若当前元素频次大于堆顶元素频次，则弹出堆顶元素，再将当前元素及其频次的元组加入堆中。
        4. 最后，将最小堆中的元素依次取出，只取元素部分（去掉频次信息），组成列表作为前k个高频元素返回。

        参数：
        - nums: 输入的整数数组
        - k: 要获取的前k个高频元素的数量

        返回：
        返回一个列表，包含数组nums中出现频率前k高的元素
        """
        # 步骤一：统计每个元素的出现频次
        frequency_dict = {}
        for num in nums:
            if num in frequency_dict:
                frequency_dict[num] += 1
            else:
                frequency_dict[num] = 1

        # 步骤二：构建最小堆
        heap = []
        for num, frequency in frequency_dict.items():
            # 将元素及其频次的元组加入堆中
            heapq.heappush(heap, (frequency, num))
            if len(heap) > k:
                # 如果堆大小超过k，弹出堆顶元素（频次最小的元素）
                heapq.heappop(heap)

        # 步骤三：获取前K个高频元素
        result = []
        for frequency, num in heap:
            result.append(num)

        return result

解法三：桶排序法

from typing import List


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """
        解法三：桶排序法

        思路：
        1. 首先使用字典统计数组nums中每个元素的出现频次。
        2. 创建一个桶，桶的数量为数组nums长度加1，桶的下标表示元素的出现频次，桶内存储出现该频次的元素列表。
        3. 遍历统计频次的字典，对于每个元素及其频次：
            - 根据频次获取对应的桶下标，将元素添加到该下标对应的桶中（如果桶为空则先创建一个空列表再添加）。
        4. 从桶的末尾开始倒序遍历桶，只要结果列表中的元素数量小于k：
            - 如果当前桶不为若为空，将桶内的所有元素添加到结果列表中。
        5. 最后，结果列表中存储的就是数组nums中出现频率前k高的元素，将其返回。

        参数：
        - nums: 输入的整数数组
        - k: 要获取的前k个高频元素的数量

        返回：
        返回一个列表，包含数组nums中出现频率前k高的元素
        """
        # 步骤一：统计每个元素的出现频次
        frequency_dict = {}
        for num in nums:
            if num in frequency_dict:
                frequency_dict[num] += 1
            else:
                frequency_dict[num] = 1

        # 步骤二：桶排序
        # 创建桶，桶的数量为数组长度加1，每个桶初始化为空列表
        buckets = [[] for _ in range(len(nums) + 1)]
        for key, frequency in frequency_dict.items():
            # 根据频次将元素放入对应的桶中
            buckets[frequency].append(key)

        # 步骤三：获取前K个高频元素
        result = []
        for i in range(len(buckets) - 1, -1, -1):
            if buckets[i] and len(result) < k:
                result.extend(buckets[i])

        return result