当前位置：首页 > news >正文

【LeetCode 热题 100】347. 前 K 个高频元素——（解法三）桶排序

news 2025/8/7 8:08:44

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

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)

整体思路

这段代码同样旨在解决 “前 K 个高频元素” 问题。它采用了一种非常巧妙且在特定情况下极为高效的 桶排序 策略。这种方法的时间复杂度可以达到线性级别，是此问题的一个重要优化方向。

算法的整体思路可以分解为以下三个步骤：

第一步：频率统计
- 与之前的所有方法一样，算法首先使用一个 哈希表 (HashMap) frequencyMap 来高效地统计数组 nums 中每个数字出现的频率。
- 这是后续桶排序的基础。
第二步：桶排序——按频率分桶
- 这是算法的核心。它创建了一个“桶”数组 buckets。
- 桶的定义：buckets 是一个列表数组，buckets[i] 这个“桶”被设计用来存储所有出现频率恰好为 i 的数字。
- 桶的大小：数组的长度设置为 nums.length + 1，因为一个数字的出现频率最高不可能超过 nums 的总长度 n。
- 装桶：算法遍历 frequencyMap 中的每一个键值对（{数字, 频率}）。对于一个条目 {num, freq}，它将 num 放入索引为 freq 的那个桶中，即 buckets[freq].add(num)。
- 这一步结束后，所有数字都被按照它们的出现频率分门别类地放进了不同的桶里。
第三步：逆序提取结果
- 由于 buckets 数组的索引本身就代表了频率，并且是天然有序的，所以我们不再需要进行任何显式的排序操作。
- 算法从 buckets 数组的末尾（即最高频率）开始向前遍历。
- 对于每个非空的桶 buckets[i]，它里面的所有数字都是当前能找到的频率最高的数字。
- 将这些桶里的数字依次填入结果数组 ans 中，直到填满 k 个元素为止。
- 返回 ans 数组。

这种方法用空间换时间，通过创建一个与频率范围相关的桶结构，巧妙地规避了基于比较的排序（如 O(M log M) 或 O(M log k)），从而实现了线性时间的解决方案。

完整代码

class Solution {/*** 找出数组中出现频率最高的前 k 个元素。（桶排序法）* @param nums 整数数组* @param k 需要找出的元素个数* @return 包含前 k 个高频元素的数组*/public int[] topKFrequent(int[] nums, int k) {// 步骤 1: 使用 HashMap 统计每个数字的出现频率Map<Integer, Integer> frequencyMap = new HashMap<>();for (int num : nums) {frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);}// 步骤 2: 创建桶，并按频率将数字放入相应的桶中// 桶的索引代表频率，桶的内容是具有该频率的数字列表// 数组长度为 nums.length + 1，因为频率最高为 nums.lengthList<Integer>[] buckets = new ArrayList[nums.length + 1];// 初始化每个桶为一个空的 ArrayListArrays.setAll(buckets, i -> new ArrayList<>());// 遍历频率 map，将数字放入对应的频率桶for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {buckets[entry.getValue()].add(entry.getKey());}// 步骤 3: 从后向前（从高频率到低频率）遍历桶，提取前 k 个元素int j = 0; // ans 数组的指针int[] ans = new int[k];// 从最高频率的桶开始遍历for (int i = nums.length; i >= 0 && j < k; i--) {// 如果当前频率的桶不为空if (!buckets[i].isEmpty()) {// 将该桶中的所有数字加入结果数组for (int num : buckets[i]) {ans[j++] = num;// 如果已经找到了 k 个，可以提前终止if (j == k) {break;}}}}return ans;}
}

时空复杂度

时间复杂度：O(N)

频率统计：遍历 nums 数组一次，填充哈希表。时间复杂度为 O(N)。
装桶：遍历 frequencyMap 一次。map 中最多有 N 个条目（最坏情况下是 M=N）。此步骤时间复杂度为 O(M)，其中 M 是唯一元素的数量。
提取结果：
- 外层 for 循环从 nums.length 遍历到 0，执行 N+1 次。
- 内层 for 循环遍历桶中的数字。虽然有嵌套循环，但每个唯一数字 num 只会被装入一个桶，也只会被从桶中提取一次。因此，所有内层循环的总执行次数等于唯一元素的数量 M。
- 所以，提取结果的总时间复杂度为 O(N) (外层循环) + O(M) (所有内层循环) = O(N)。

综合分析：
总时间复杂度 = O(N) (统计) + O(M) (装桶) + O(N) (提取)。
由于 M <= N，所以总的时间复杂度可以简化为 O(N)。这是解决此问题的最优时间复杂度。

空间复杂度：O(N)

主要存储开销：
- HashMap frequencyMap: 需要存储所有 M 个唯一元素及其频率。空间为 O(M)。
- List<Integer>[] buckets: 这是一个长度为 N+1 的数组，它存储了所有 M 个唯一数字。所以 buckets 数组本身的大小是 O(N)，其内部所有 ArrayList 存储的元素总数是 M。因此，这部分占用的总空间是 O(N + M)。