求解序列中第k大与第k小的差值问题

好的，我们来一步步解决这个问题。 ## 问题分析 给定一个长度为 `n` 的正整数序列，我们需要计算： - 第 `k` 大的数 - 第 `k` 小的数 然后求出它们的差。 **关键点**： - 第 `k` 小的数：升序排列后的第 `k` 个元素（索引从1开始）。 - 第 `k` 大的数：降序排列后的第 `k` 个元素，等价于升序排列后的第 `n - k + 1` 个元素。 最直接的方法是将数组排序，然后分别取出这两个位置的值并相减。 --- ## 复杂度分析 - 排序时间复杂度：`O(n log n)` - 空间复杂度：`O(1)`（若允许在原数组上排序） --- ## 代码实现（C++） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } // 升序排序 sort(arr.begin(), arr.end()); // 第k小的数（索引从0开始，所以是k-1） int kthMin = arr[k - 1]; // 第k大的数 = 第 n-k+1 小的数（索引为 n-k） int kthMax = arr[n - k]; int result = kthMax - kthMin; cout << result << endl; return 0; } ``` --- ## 示例 输入： ``` 5 2 10 20 30 40 50 ``` 排序后：`[10, 20, 30, 40, 50]` - 第2小的数 = `20` - 第2大的数 = `40` - 结果 = `40 - 20 = 20` 输出： ``` 20 ``` --- ## 开发注意要点 - 确保 `k` 是有效值（1 ≤ k ≤ n）。 - 元素可能重复，但题目保证正整数，不影响逻辑。 - 如果n特别大（如10^7），可以改用`nth_element`实现O(n)的平均时间复杂度，避免完整排序。 ######[AI问答 | 530点数解答 | 2026-05-31 21:35:55]