查找正整数序列中第k大和第k小元素的Python实现

可以使用排序或快速选择算法解决这个问题。以下是 Python 实现，兼顾简洁性与效率： ```python def find_kth_largest_smallest(a, k): if not a or k < 1 or k > len(a): raise ValueError("k must be between 1 and length of array") # 排序后直接索引（适合一般场景，代码清晰） sorted_a = sorted(a) kth_largest = sorted_a[-k] # 第 k 大：从末尾数第 k 个 kth_smallest = sorted_a[k-1] # 第 k 小：从开头数第 k 个（0-indexed） return kth_largest, kth_smallest # 示例用法 a = [3, 2, 1, 5, 6, 4] k = 2 largest, smallest = find_kth_largest_smallest(a, k) print(f"第 {k} 大的元素: {largest}") # 输出: 5 print(f"第 {k} 小的元素: {smallest}") # 输出: 2 ``` ✅ 时间复杂度：`O(n log n)`（排序主导） ✅ 空间复杂度：`O(n)`（创建新排序数组） 如需 `O(n)` 平均时间（不依赖排序），可改用 `quickselect` 实现第 k 小/大，但需注意边界和重复元素处理。需要我提供该优化版本吗？ ######[AI问答 | 362点数解答 | 2026-03-29 11:34:34]