【堆】——前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

希望通过这些详细注释的代码能让你更清楚地理解每种解法的实现思路哦，如果还有其他疑问，可以随时问呀。

秒客网