Python实现K个高频元素：从频率计数到高效算法

nums = [1, 1, 1, 2, 2, 3]
iterations = {}

for x in nums:
    # 错误：x是数组中的元素值，而非索引。
    # nums[x] 会尝试将元素值作为索引去访问数组，这会导致IndexError或逻辑错误。
    if nums[x] in iterations:
        iterations[nums[x]] += 1
    else:
        iterations[nums[x]] = 1

print(iterations) # 对于 nums = [1,1,1,2,2,3]，可能输出 {1: 5, 2: 1} 或抛出 IndexError

nums = [1, 1, 1, 2, 2, 3]
frequency_map = {} # 使用更具描述性的变量名

for x in nums:
    if x in frequency_map:
        frequency_map[x] += 1
    else:
        frequency_map[x] = 1

print(frequency_map) # 正确输出: {1: 3, 2: 2, 3: 1}

from collections import Counter

nums = [1, 1, 1, 2, 2, 3]
frequency_map = Counter(nums)

print(frequency_map) # 输出: Counter({1: 3, 2: 2, 3: 1})

# 假设 frequency_map = {1: 3, 2: 2, 3: 1}
k = 2

# 将字典转换为 (元素, 频率) 元组列表
# 例如：[(1, 3), (2, 2), (3, 1)]
items = list(frequency_map.items())

# 根据频率（元组的第二个元素）进行降序排序
# key=lambda item: item[1] 指定排序依据是元组的第二个元素（频率）
# reverse=True 表示降序排列
items.sort(key=lambda item: item[1], reverse=True)

# 提取前 k 个元素的键（即元素本身）
top_k_elements = [item[0] for item in items[:k]]

print(top_k_elements) # 输出: [1, 2]

import heapq

# 假设 frequency_map = {1: 3, 2: 2, 3: 1}
k = 2

min_heap = [] # 堆中存储 (频率, 元素) 元组

for num, freq in frequency_map.items():
    # 将 (频率, 元素) 推入最小堆
    heapq.heappush(min_heap, (freq, num))
    # 如果堆的大小超过 k，则弹出堆中频率最小的元素
    if len(min_heap) > k:
        heapq.heappop(min_heap)

# 提取堆中剩余的元素（只取元素本身）
top_k_elements_heap = [item[1] for item in min_heap]

print(top_k_elements_heap) # 输出: [2, 1] (顺序可能因堆实现而异)

from collections import Counter
import heapq

def topKFrequent(nums: list[int], k: int) -> list[int]:
    """
    找出给定整数数组中出现频率最高的 k 个元素。

    Args:
        nums: 整数数组。
        k: 需要找出的高频元素数量。

    Returns:
        包含 k 个高频元素的列表。
    """
    if not nums:
        return []

    # 步骤1: 统计元素频率
    # 使用 collections.Counter 简洁高效地完成频率统计
    frequency_map = Counter(nums)

    # 步骤2: 使用最小堆找出 K 个高频元素
    # 堆中存储 (频率, 元素) 元组，最小堆会根据元组的第一个元素（频率）进行排序
    min_heap = [] 

    for num, freq in frequency_map.items():
        # 将当前元素的 (频率, 元素) 对推入最小堆
        heapq.heappush(min_heap, (freq, num))

        # 如果堆的大小超过 k，则弹出堆顶元素（即当前堆中频率最小的元素）
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    # 提取堆中剩余的元素（只取元素本身）
    # 此时堆中保留的就是频率最高的 k 个元素
    result = [item[1] for item in min_heap]

    return result

# 示例测试
nums1 = [1, 1, 1, 2, 2, 3]
k1 = 2
print(f"输入: nums={nums1}, k={k1} -> 输出: {topKFrequent(nums1, k1)}") 
# 预期输出可能为 [1, 2] 或 [2, 1]，因为顺序不重要

nums2 = [1]
k2 = 1
print(f"输入: nums={nums2}, k={k2} -> 输出: {topKFrequent(nums2, k2)}") 

nums3 = [3, 0, 1, 0]
k3 = 1
print(f"输入: nums={nums3}, k={k3} -> 输出: {topKFrequent(nums3, k3)}") 

nums4 = [1, 2]
k4 = 2
print(f"输入: nums={nums4}, k={k4} -> 输出: {topKFrequent(nums4, k4)}")