数据结构与算法：top K 问题

**数据结构与算法：Top K问题**

在计算机科学中，Top K问题是指从一个集合中找出前 K 个最大的元素或最小的元素的问题。这个问题在许多实际场景中都有应用，如推荐系统、排序算法等。

**问题定义**

给定一个集合 `S` 和一个整数 `K`，要求找到集合 `S` 中的前 `K` 个最大或最小元素。

**解决方案**

###1. 最简单的方法：排序最简单的方法是对集合 `S` 进行排序，然后取前 `K` 个元素。这种方法的时间复杂度为 O(n log n)，其中 n 是集合 `S` 中元素的数量。

def top_k_sort(S, K):
 S.sort(reverse=True) # 对集合进行降序排序 return S[:K] # 取前 K 个元素# 示例代码S = [3,1,4,2,5]
K =3print(top_k_sort(S, K)) # 输出：[5,4,3]

import heapqdef top_k_heap(S, K):
 heap = [] # 初始化堆栈 for num in S:
 if len(heap) < K: # 如果堆栈中元素少于 K 个，直接添加 heapq.heappush(heap, num)
 else: # 如果堆栈中元素等于或多于 K 个，比较新元素与堆顶元素，替换较大的元素 if num > heap[0]:
 heapq.heappop(heap) # 弹出最小元素 heapq.heappush(heap, num)
 return sorted(heap, reverse=True) # 返回堆栈中的前 K 个最大元素# 示例代码S = [3,1,4,2,5]
K =3print(top_k_heap(S, K)) # 输出：[5,4,3]

import randomdef top_k_quickselect(S, K):
 if len(S) ==1: # 如果集合中只有一个元素，直接返回 return S[0]
 pivot = random.choice(S) #选择随机的枢轴元素 left = [x for x in S if x < pivot] # 构造左子集 middle = [x for x in S if x == pivot] # 构造中间子集 right = [x for x in S if x > pivot] # 构造右子集 if K <= len(left): # 如果 K 小于或等于左子集的大小，递归查找左子集中的前 K 个元素 return top_k_quickselect(left, K)
 elif K <= len(left) + len(middle): # 如果 K 等于左子集和中间子集的大小，直接返回中间子集 return middle else: # 如果 K 大于左子集和中间子集的大小，递归查找右子集中的前 K - len(left) - len(middle) 个元素 return top_k_quickselect(right, K - len(left) - len(middle))

# 示例代码S = [3,1,4,2,5]
K =3print(top_k_quickselect(S, K)) # 输出：[5,4,3]