高效解决“前 K 个高频元素”问题：基于桶排序的Java实现与关键细节解析

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计每个数字的频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // ... 后续步骤
    }
}

        // ... (接上文代码)

        // 2. 创建频率桶
        // bucket[i] 存储所有频率为 i 的数字列表
        List<Integer>[] bucket = new ArrayList[nums.length + 1];

        // 遍历频率映射的键集，将数字放入对应的频率桶
        for (int num : freqMap.keySet()) { // 关键点：遍历 freqMap.keySet()
            int frequency = freqMap.get(num);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(num);
        }

        // ... 后续步骤

        // 错误示例：遍历原始 nums 数组填充桶
        for (int num : nums) { // 错误！
            int frequency = freqMap.get(num);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(num); // 可能会添加重复元素到桶中
        }

        // ... (接上文代码)

        // 3. 从桶中提取前 K 个高频元素
        int[] result = new int[k];
        int resultIndex = 0; // 用于填充结果数组的索引

        // 从最高频率开始（桶数组末尾）向前遍历
        for (int i = bucket.length - 1; i >= 0 && resultIndex < k; i--) {
            if (bucket[i] != null) {
                for (int element : bucket[i]) {
                    result[resultIndex++] = element;
                    if (resultIndex == k) { // 如果已收集到 K 个元素，则提前返回
                        return result;
                    }
                }
            }
        }
        return result; // 理论上不会执行到这里，因为 k 总是小于等于总的唯一元素数
    }
}

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计每个数字的频率
        // Key: 数字本身, Value: 该数字出现的频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // 2. 创建频率桶
        // bucket[i] 存储所有频率为 i 的数字列表
        // 桶数组的大小为 nums.length + 1，因为最大频率不可能超过 nums.length
        List<Integer>[] bucket = new ArrayList[nums.length + 1];

        // 遍历频率映射的键集 (keySet)，将每个唯一的数字放入其对应的频率桶中
        // 这样做保证了每个桶中存储的数字都是唯一的
        for (int num : freqMap.keySet()) {
            int frequency = freqMap.get(num);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(num);
        }

        // 3. 从桶中提取前 K 个高频元素
        int[] result = new int[k];
        int resultIndex = 0; // 用于填充结果数组的当前索引

        // 从最高频率开始（桶数组的末尾）向前遍历
        // 循环条件 resultIndex < k 确保我们只收集 K 个元素
        for (int i = bucket.length - 1; i >= 0 && resultIndex < k; i--) {
            if (bucket[i] != null) { // 检查当前频率桶是否为空
                for (int element : bucket[i]) { // 遍历当前频率桶中的所有数字
                    result[resultIndex++] = element; // 将数字添加到结果数组
                    if (resultIndex == k) { // 如果已收集到 K 个元素，则立即返回结果
                        return result;
                    }
                }
            }
        }
        return result; // 正常情况下，当 resultIndex 达到 k 时会提前返回
    }
}