C++实现序列第k大与第k小之差

根据题目要求，我们需要计算序列中第 k 大的数减去第 k 小的数的值。核心思路是：先对序列排序，第 k 小的数就是排序后第 k-1 个元素（0-indexed），第 k 大的数就是排序后第 n-k 个元素（因为第1大是最大，即索引 n-1，第 k 大是索引 n-k）。两者相减即可。 若序列中有重复元素，排序后依然有效，因为“第 k 小”和“第 k 大”的定义基于排序后的位置（从1计数）。 实现方式：使用 `std::sort` 排序，时间复杂度 O(n log n)，满足一般需求。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end()); int kth_small = a[k-1]; // 第 k 小（从1计数） int kth_large = a[n-k]; // 第 k 大（从1计数，对应索引 n-k） cout << kth_large - kth_small << "\n"; return 0; } ``` ## ⚙️ 复杂度分析 - 时间：O(n log n)，排序主导。 - 空间：O(n)，存储序列。 ## 💡 实现注意 - 索引计算：第 k 小（1≤k≤n）对应 `a[k-1]`；第 k 大对应 `a[n-k]`。 - 若 k 超出范围（如 k>n），则未定义，题目默认合法。 - 输入使用快读，避免大数据量超时。 ######[AI问答 | 430点数解答 | 2026-08-07 23:40:11]