利用排序快速计算第k大与第k小的差值

好的，针对您所描述的题目，这是一个典型的利用排序后直接取值并计算差值的算法问题。下面我会分步骤说明解决方案，并给出完整的代码实现。 ## 📘 题目分析 题目要求我们从一个正整数序列中，分别找出**第k大的数**和**第k小的数**，然后计算二者的差值。 **关键点理解** - 第k小的数：从小到大排序，索引为k-1（因为数组从0开始）。 - 第k大的数：从小到大排序，倒数第k个数，索引为`n - k`。 - `n`最大10000，使用快速排序或内置排序函数完全可行。 ## 🧩 算法思路 1. 读取输入 `n` 和 `k`，以及整个数列。 2. 对数列进行升序排序。 3. 第k小的数 = `sorted_array[k-1]` 4. 第k大的数 = `sorted_array[n-k]` 5. 输出差值：第k大的数减去第k小的数。 ## 🛠️ 代码实现（C++ 为例） ```cpp #include <iostream> #include <algorithm> #include <vector> 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_small = arr[k - 1]; int kth_large = arr[n - k]; int result = kth_large - kth_small; cout << result << endl; return 0; } ``` ## 📌 代码注释说明 - `sort(arr.begin(), arr.end())`：对数组进行升序排序。 - `arr[k-1]`：第k小的元素（因为排序后索引0对应第1小）。 - `arr[n-k]`：第k大的元素（倒数第k个，索引从0开始）。 - 直接相减得到结果，无需额外判断符号（题目保证大数减小数不会为负数，因为第k大的数总是大于等于第k小的数）。 ## 🧪 测试样例验证 **样例1** ``` 输入： 3 1 5 1 3 排序后：[1, 3, 5] 第1小 = 1，第1大 = 5 差值 = 4 ✅ ``` **样例2** ``` 输入： 5 2 3 2 5 1 4 排序后：[1, 2, 3, 4, 5] 第2小 = 2，第2大 = 4 差值 = 2 ✅ ``` ## 🎯 时间和空间复杂度 - 时间复杂度：O(n log n)，主要由排序决定，适合n≤10000。 - 空间复杂度：O(n)，用于存储原序列。 ######[AI问答 | 662点数解答 | 2026-05-31 21:36:40]