LeetCode-热题100：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 <= 10⁵
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

代码及注释

func topKFrequent(nums []int, k int) []int {
    // 初始化结果集
    res := make([]int, 0)
    // 统计每个数字出现的频率
    frequency := make(map[int]int)
    // 使用桶排序，桶的索引表示数字的频率
    bucket := make([][]int, len(nums) + 1)
    
    // 统计每个数字的出现频率
    for i := 0; i < len(nums); i++ {
        frequency[nums[i]] += 1
    }

    // 将数字按频率放入对应的桶中
    for num, freq := range frequency {
        bucket[freq] = append(bucket[freq], num)
    }

    // 从桶的末尾开始，将数字添加到结果集中，直到结果集大小达到k
    for i := len(bucket) - 1; i >= 0 && len(res) < k; i-- {
        if len(bucket[i]) > 0 {
            res = append(res, bucket[i]...)
        }
    }
    // 返回前k个高频元素
    return res[:k]
}

代码解释

1. 哈希表统计频率：

   for i := 0; i < len(nums); i++ {
       frequency[nums[i]] += 1
   }
   

   使用哈希表frequency来统计每个数字的出现频率。这样做的好处是可以在O(n)的时间复杂度内完成频率的统计。

2. 桶排序：

   bucket := make([][]int, len(nums) + 1)
   for num, freq := range frequency {
       bucket[freq] = append(bucket[freq], num)
   }
   

   由于频率的范围是从1到len(nums)，所以我们可以使用桶排序来按频率存储数字。桶的索引表示数字的频率，桶中的元素是具有相同频率的数字。这样做的目的是为了更高效地找到前k高频的数字。

3. 从桶的末尾开始遍历：

   for i := len(bucket) - 1; i >= 0 && len(res) < k; i-- {
       if len(bucket[i]) > 0 {
           res = append(res, bucket[i]...)
       }
   }
   

   从桶的末尾开始遍历，这样可以确保我们首先考虑的是出现频率最高的数字。只有当结果集res的大小小于k时，我们才将桶中的数字添加到res中。

4. 返回前k个高频元素：

   return res[:k]
   

   最后，我们返回结果集res的前k个元素，这就是题目要求的前k高频元素。

这种方法的时间复杂度是O(n)，其中n是数组的长度。这是因为我们首先需要遍历数组来统计每个数字的频率，然后我们需要将数字按频率放入对应的桶中，最后我们遍历桶来找到前k高频的数字。