C++ 求第k大减第k小值：排序后直接计算

## 🧮 解题思路 题目要求计算第 k 大的数减去第 k 小的数。 核心在于：序列排序后，第 k 小的数位于下标 `k-1`（0-indexed），第 k 大的数位于下标 `n-k`。 直接对数组排序，然后计算 `arr[n-k] - arr[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()); int kth_smallest = arr[k-1]; int kth_largest = arr[n-k]; cout << kth_largest - kth_smallest << endl; return 0; } ``` ## 📊 复杂度分析 - 时间复杂度：O(n log n)，主要来自排序。 - 空间复杂度：O(1) 额外空间（不考虑输入存储）。 ## ⚠️ 注意事项 - 输入保证 `k ≤ n`，且所有数为正整数。 - 若 `k = 1`，则第 1 小为最小值，第 1 大为最大值，结果为正数或零。 - 使用 `long long` 可避免极端数据溢出（题目未说明范围，建议改用 `long long` 类型更安全）。 ######[AI问答 | 379点数解答 | 2026-08-09 22:09:32]