Top K Elements (前 K 个高频元素)

在数据结构与算法（DSA）中，Top K Elements（前K个元素）指的是从一个数据集中，找到最重要的K个元素，这些元素通常是满足某种条件的最“最值”，比如最大、最小、最频繁等。

通俗解释：

想象一下你有一组数字，可能是从一个大文件中读取的，或者是网络上抓取的数据。现在你希望从中找出最大或最小的K个数字，或者找出出现次数最多的K个数字，等等。

常见问题：

1. 找出前K大的数：从一个数字列表中找出最大的K个数字。
2. 找出前K小的数：从一个数字列表中找出最小的K个数字。
3. 找出出现次数最多的前K个元素：例如，在一堆单词中找出出现频率最高的K个单词。

解决方法：

为了高效地找到这些元素，我们可以使用不同的数据结构和算法来优化搜索过程。常见的方法包括：

1. 使用堆（Heap）：堆是一种完全二叉树结构，可以在O(log n)时间复杂度内进行插入和删除操作，非常适合用于寻找前K大或前K小的元素。
2. 排序：直接将数组排序，然后选择前K个元素，时间复杂度是O(n log n)，但是在某些情况下可能不如堆高效。
3. 快速选择算法（QuickSelect）：这是一种类似于快速排序的算法，可以在O(n)时间内找到第K大的元素，适用于只需要找到某个位置的元素时。

1. 找前K大的元素：用堆

如果你想找到前K大的元素，可以使用最小堆来解决：

• 维护一个堆，堆的大小始终为K。
• 遍历所有元素，每次将当前元素与堆顶元素比较：
  • 如果当前元素比堆顶元素大，就替换堆顶元素。
  • 如果当前元素不大，就跳过。

这样，堆中的K个元素就保持了前K大的元素。

代码示例：

import heapq

def top_k_largest(nums, k):
    # 使用最小堆，堆大小为k
    heap = nums[:k]
    heapq.heapify(heap)  # 创建一个堆
    for num in nums[k:]:
        if num > heap[0]:  # 如果当前数字大于堆顶元素（堆中的最小元素）
            heapq.heapreplace(heap, num)  # 替换堆顶元素
    return heap  # 返回堆中的K个元素（最小堆）

2. 找前K小的元素：同样用堆

如果你想找前K小的元素，可以使用最大堆来处理：

• 同样地，维护一个堆，堆的大小为K。
• 遍历所有元素，每次将当前元素与堆顶元素比较：
  • 如果当前元素比堆顶元素小，就替换堆顶元素。

代码示例：

import heapq

def top_k_smallest(nums, k):
    # 使用最大堆，堆大小为k
    heap = [-num for num in nums[:k]]  # 把所有元素取负，转化成最大堆
    heapq.heapify(heap)
    for num in nums[k:]:
        if -num > heap[0]:  # 如果当前数字小于堆顶元素
            heapq.heapreplace(heap, -num)  # 替换堆顶元素
    return [-num for num in heap]  # 转换回原来的正数

3. 找出现频率最高的前K个元素：用哈希表 + 堆

如果你要找出现次数最多的前K个元素，可以结合哈希表和堆：

• 使用哈希表统计每个元素的出现频率。
• 然后使用堆来找到频率最高的K个元素。

代码示例：

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    # 统计每个元素的频率
    count = Counter(nums)
    # 使用堆来找前K个频率最高的元素
    return [item[0] for item in heapq.nlargest(k, count.items(), key=lambda x: x[1])]

复杂度分析：

1. 堆法：每次插入或替换堆顶元素的时间复杂度为O(log k)，因此处理n个元素的时间复杂度为O(n log k)。
2. 排序法：先对数组排序的时间复杂度为O(n log n)，然后选择前K个元素，所以时间复杂度为O(n log n)。
3. 快速选择法：通过快速选择算法可以在O(n)时间内找到第K大的元素，但适用于一些特殊的查找问题。

总结：

Top K Elements（前K个元素）是一个非常常见的问题，应用广泛，涉及到找到某个集合中的最大或最小的K个元素，或者找到频率最高的K个元素。常用的方法包括堆、排序和快速选择等，堆是一种非常高效的方式，特别适合处理动态更新的场景，时间复杂度为O(n log k)。

LeetCode 相关题目:

已完成题目: