查找正整数序列中第k小与第k大元素的两种高效实现方案

可以使用排序或快速选择算法解决这个问题。下面提供两种实现方式： ### 方法一：排序法（简单直观） 对数组升序排序后，第 k 小为 `a[k-1]`，第 k 大为 `a[n-k]`（n 为长度）。 ```python def find_kth_min_max_sort(a, k): if not a or k < 1 or k > len(a): raise ValueError("k must be between 1 and length of array") b = sorted(a) # 升序副本 n = len(b) kth_min = b[k-1] kth_max = b[n-k] return kth_min, kth_max # 示例 a = [3, 2, 1, 5, 6, 4] k = 2 min_val, max_val = find_kth_min_max_sort(a, k) print(f"第 {k} 小: {min_val}, 第 {k} 大: {max_val}") # 输出：第 2 小: 2, 第 2 大: 5 ``` ### 方法二：快速选择（平均 O(n)，更高效） 利用 `nth_element` 思想，不完全排序即可定位第 k 小/大元素。Python 中可用 `heapq` 实现： ```python import heapq def find_kth_min_max_heap(a, k): if not a or k < 1 or k > len(a): raise ValueError("k must be between 1 and length of array") n = len(a) # 第 k 小：维护大小为 k 的最大堆（或直接用 heapq.nsmallest） kth_min = heapq.nsmallest(k, a)[-1] # 第 k 大：维护大小为 k 的最小堆（或用 heapq.nlargest） kth_max = heapq.nlargest(k, a)[-1] return kth_min, kth_max # 示例 a = [3, 2, 1, 5, 6, 4] k = 2 min_val, max_val = find_kth_min_max_heap(a, k) print(f"第 {k} 小: {min_val}, 第 {k} 大: {max_val}") # 输出同上 ``` 两种方法均支持重复元素，且结果符合常规定义（如 `[1,2,2,3]` 中第 2 小是 `2`，第 2 大是 `2`）。 ######[AI问答 | 583点数解答 | 2026-03-29 11:34:08]