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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-11-16

浏览次数：次

返回列表

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

本文详细介绍了如何在Python中高效地统计数组中元素的出现频率，这是解决“K个高频元素”问题的关键一步。我们将探讨使用哈希映射（字典）进行计数的正确方法，纠正常见编码错误，并为读者提供清晰的示例代码。在此基础上，文章进一步讲解了如何利用排序和最小堆两种策略，从频率统计结果中筛选出K个最高频率元素，并给出了完整的解决方案及注意事项。

理解“K个高频元素”问题

“K个高频元素”问题是一个常见的算法挑战，其目标是从一个给定的整数数组 nums 中，找出出现频率最高的 k 个元素。元素的返回顺序可以不固定。

例如：

给定 nums = [1, 1, 1, 2, 2, 3] 和 k = 2。
元素 1 出现 3 次。
元素 2 出现 2 次。
元素 3 出现 1 次。
频率最高的 2 个元素是 1 和 2。

解决这个问题通常分为两个主要步骤：

统计数组中每个元素的出现频率。
根据频率从高到低筛选出前 k 个元素。

步骤一：高效统计元素频率

统计元素频率最直观且高效的方法是使用哈希映射（在Python中即为字典）。哈希映射可以提供接近 O(1) 的平均时间复杂度进行插入和查找操作。

常见错误与修正

在实现频率统计时，一个常见的错误是混淆迭代器变量的含义。考虑以下错误代码示例：

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

上述代码的问题在于，for x in nums: 循环中的 x 直接代表了 nums 列表中的每个元素的值，而不是它的索引。因此，正确的做法是直接使用 x 作为字典的键来统计其频率，而不是 nums[x]。

修正后的频率统计代码：

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}

这段代码遍历 nums 列表，对于每个元素 x：

如果 x 已经在 frequency_map 中作为键存在，则将其对应的频率值加 1。
如果 x 不在 frequency_map 中，则将其添加为新键，并将频率初始化为 1。

更Pythonic的频率统计方法：使用 collections.Counter

Python标准库 collections 模块提供了一个 Counter 类，它专门用于高效地计数可哈希对象的出现次数。这是处理频率统计任务时最推荐的方法。

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})

Counter 对象是一个字典的子类，它以元素为键，以其出现次数为值。其初始化和使用都非常简洁高效。

Zyro AI Background Remover

Zyro推出的AI图片背景移除工具

145 查看详情 Zyro AI Background Remover

步骤二：筛选K个高频元素

在得到元素的频率映射 frequency_map 后，我们需要从中选出频率最高的 k 个元素。这里介绍两种常用的方法：

方法一：排序法

最直接的方法是将频率映射转换为一个列表，然后根据频率进行排序，最后取出前 k 个元素。

# 假设 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]

时间复杂度分析：

将字典转换为列表：O(N)，其中 N 是唯一元素的数量。
排序：O(N log N)。
提取前 k 个元素：O(k)。
总时间复杂度：O(N log N)。

方法二：最小堆（优先队列）法

当 k 远小于唯一元素的总数 N 时，使用最小堆（min-heap）通常比完全排序更高效。最小堆可以帮助我们维护一个大小为 k 的数据结构，其中包含当前频率最高的 k 个元素。

基本思想：

创建一个大小为 k 的最小堆。堆中存储 (频率, 元素) 对。
遍历 frequency_map 中的每个 (元素, 频率) 对。
将 (频率, 元素) 对推入最小堆。
如果堆的大小超过 k，则弹出堆顶元素（即当前堆中频率最小的元素）。
遍历结束后，堆中剩下的 k 个元素就是频率最高的 k 个元素。

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] (顺序可能因堆实现而异)

时间复杂度分析：

遍历 frequency_map：O(N)，其中 N 是唯一元素的数量。
每次堆操作（heappush 或 heappop）：O(log k)。
总时间复杂度：O(N log k)。

当 k 远小于 N 时，O(N log k) 优于 O(N log N)。

完整解决方案示例

结合上述步骤，以下是使用 collections.Counter 和最小堆的完整 Python 解决方案：

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)}")

注意事项与总结

理解迭代行为： 在 Python 中，for item in collection: 结构会直接遍历 collection 中的每个 item，而不是索引。这是初学者常犯的错误点，务必区分 item 和 collection[item] 的含义。
选择合适的数据结构： 对于频率统计，collections.Counter 是 Python 中最简洁和高效的选择。对于需要动态维护前 k 个最大/最小元素的场景，堆（优先队列）是理想的数据结构。
时间复杂度考量：
- 简单排序法的时间复杂度为 O(N log N)，其中 N 是唯一元素的数量。
- 最小堆法的时间复杂度为 O(N log k)，其中 N 是唯一元素的数量，k 是目标数量。当 k 远小于 N 时，堆法效率更高。
边缘情况处理： 在实际应用中，需要考虑输入数组为空、k 值小于等于 0、k 值大于唯一元素数量等边缘情况。上述 topKFrequent 函数已包含对空数组的简单处理。
输出顺序： 问题通常不要求高频元素的特定输出顺序，因此排序和堆方法返回的顺序可能不同，但这不影响结果的正确性。