序列第k大与第k小的差值计算：排序法详解

## 🔍 问题解析 题目要求从长度为 n 的序列中，找出第 k 大的数和第 k 小的数，然后计算它们的差值。需要确保理解“第 k 大”和“第 k 小”的定义。 第 k 大的数是指按降序排列后位于第 k 个位置的数，第 k 小的数是指按升序排列后位于第 k 个位置的数。由于正整数序列，且 k 可能大于 n 吗？通常题目会保证 1 ≤ k ≤ n，但这里并未明确，需按常规处理：若 k 超出范围，可能无解，但按题目描述，应默认 k 有效。 ## 💡 解决思路 直接做法：对数组排序。排序后，第 k 小的数是排序后索引 k-1 的元素（0-based），第 k 大的数是排序后索引 n-k 的元素。差值即为这两个数的差。 时间复杂度 O(n log n)，空间复杂度 O(1)（若允许修改原数组）或 O(n)。 ## 📝 代码实现（Python） ```python def diff_kth_largest_smallest(arr, k): # 深拷贝避免修改原数组 sorted_arr = sorted(arr) n = len(sorted_arr) if k < 1 or k > n: return None # 或抛出异常 kth_smallest = sorted_arr[k-1] kth_largest = sorted_arr[n-k] return kth_largest - kth_smallest # 示例 arr = [3, 1, 4, 1, 5, 9, 2, 6] k = 3 result = diff_kth_largest_smallest(arr, k) print(f"第{k}大与第{k}小的差值为: {result}") ``` ## 🧮 算法步骤 1. 将输入序列拷贝并排序。 2. 获取序列长度 n。 3. 检查 k 是否在有效范围内。 4. 第 k 小的数 = sorted_arr[k-1]。 5. 第 k 大的数 = sorted_arr[n-k]。 6. 计算差值并返回。 ## ⏱️ 复杂度分析 排序时间复杂度 O(n log n)，空间复杂度 O(n)（额外数组）。 ## 📌 注意事项 排序后索引计算要小心，特别是 n-k 可能出现等于 n 的情况？当 k=1 时，n-k = n-1，正确。当 k=n 时，n-k=0，正确。确保 k 在 [1, n] 时，索引安全。 ## 🎯 测试示例 输入：arr = [10, 2, 5, 7, 3, 8, 1], k=2 排序后 [1,2,3,5,7,8,10]，第2小=2，第2大=8，差值=6。 ######[AI问答 | 654点数解答 | 2026-08-07 23:48:48]