哈希算法题目：分桶法解决大数据量的Top K频繁元素问题

题目描述
给定一个非常大的整数数组（数据量可能达到亿级别），找出出现频率最高的前K个元素。要求时间复杂度优于O(n log n)，且内存使用要高效。

解题思路分析
这个问题需要结合哈希表和分桶思想：

1. 使用哈希表统计每个元素的频率（O(n)时间复杂度）
2. 使用分桶法按频率分组，避免全局排序
3. 从高频桶开始收集元素，直到凑够K个

详细解题步骤

步骤1：频率统计

def count_frequency(nums):
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    return freq_map

• 遍历数组，用哈希表记录每个数字出现的次数
• 时间复杂度：O(n)，空间复杂度：O(m)（m为不同数字的个数）

步骤2：按频率分桶

def create_frequency_buckets(freq_map):
    max_freq = max(freq_map.values()) if freq_map else 0
    buckets = [[] for _ in range(max_freq + 1)]
    
    for num, freq in freq_map.items():
        buckets[freq].append(num)
    
    return buckets

• 创建长度为max_freq+1的桶数组
• 每个桶存储对应频率的所有数字
• 例如：buckets[3]存储所有出现3次的数字

步骤3：从高到低收集Top K元素

def top_k_frequent(nums, k):
    freq_map = count_frequency(nums)
    buckets = create_frequency_buckets(freq_map)
    
    result = []
    for i in range(len(buckets) - 1, 0, -1):
        if not buckets[i]:
            continue
        result.extend(buckets[i])
        if len(result) >= k:
            break
    
    return result[:k]

• 从最高频率的桶开始向后遍历
• 将每个桶中的元素添加到结果集中
• 当结果集元素数量≥K时停止收集

复杂度分析

• 时间复杂度：O(n) - 统计频率O(n)，分桶O(m)，收集结果O(k)
• 空间复杂度：O(n) - 哈希表和桶的空间

实际应用优化
对于海量数据场景，可以采用以下优化：

1. 使用更紧凑的数据结构存储哈希表
2. 对于频率很低的元素可以提前过滤
3. 结合堆结构处理边界情况

这种方法避免了全局排序，在保持线性时间复杂度的同时，有效控制了内存使用。