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

以下是使用 Python 实现找到正整数序列中第 `k` 大的元素和第 `k` 小的元素的代码： ```python def find_kth_elements(arr, k): # 对序列进行排序 sorted_arr = sorted(arr) # 第 k 小的元素 kth_smallest = sorted_arr[k - 1] # 第 k 大的元素 kth_largest = sorted_arr[-k] return kth_smallest, kth_largest # 示例序列 a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] k = 3 # 调用函数 kth_smallest, kth_largest = find_kth_elements(a, k) print(f"第 {k} 小的元素是: {kth_smallest}") print(f"第 {k} 大的元素是: {kth_largest}") ``` ### 代码解释 1. **定义函数 `find_kth_elements`**：函数接收一个列表 `arr` 和一个整数 `k` 作为参数。 2. **对列表进行排序**：使用 `sorted` 函数对列表进行排序，得到一个升序排列的新列表 `sorted_arr`。 3. **找到第 `k` 小的元素**：在排序后的列表中，第 `k` 小的元素位于索引 `k - 1` 处。 4. **找到第 `k` 大的元素**：在排序后的列表中，第 `k` 大的元素位于索引 `-k` 处。 5. **返回结果**：返回第 `k` 小的元素和第 `k` 大的元素。 ### 复杂度分析 - **时间复杂度**：排序操作的时间复杂度为 $O(n log n)$，其中 $n$ 是列表的长度。 - **空间复杂度**：排序操作需要额外的 $O(n)$ 空间。 ######[AI问答 | 487点数解答 | 2026-03-29 11:33:42]