C++实现序列第k大与第k小的差值计算

### 💻代码实现 ```cpp #include <iostream> #include <algorithm> #include <vector> int main() { int n, k; // 读取序列长度 n 和 k 的值 std::cin >> n >> k; std::vector<int> a(n); // 读取序列元素 for (int i = 0; i < n; ++i) { std::cin >> a[i]; } // 对序列进行排序 std::sort(a.begin(), a.end()); // 计算第 k 大的数和第 k 小的数的差值 int result = a[n - k] - a[k - 1]; // 输出结果 std::cout << result << std::endl; return 0; } ``` ### 🔍代码解释 - **输入部分**：使用 `std::cin` 读取序列长度 `n` 和 `k` 的值，然后读取整个序列并存储在 `std::vector<int>` 类型的 `a` 中。 - **排序部分**：使用 `std::sort` 函数对 `std::vector<int>` 中的元素进行排序，默认是升序排列。 - **计算差值部分**：根据数组索引的特性，第 `k` 小的元素索引为 `k - 1`，第 `k` 大的元素索引为 `n - k`，计算二者差值并存储在 `result` 中。 - **输出结果**：使用 `std::cout` 输出计算得到的差值。 ### ⚙️复杂度分析 - **时间复杂度**：排序操作的时间复杂度为 $O(n log n)$，其中 `n` 是序列的长度。后续计算差值的时间复杂度为常数时间 $O(1)$。整个程序的时间复杂度是 $O(n log n)$。 - **空间复杂度**：主要使用了一个长度为 `n` 的 `std::vector` 来存储序列元素，因此空间复杂度为 $O(n)$。 ### 💡开发建议 - **输入合法性检查**：在实际应用中，应该对输入的 `n` 和 `k` 进行合法性检查，确保它们满足题目的数据范围。可以添加如下代码： ```cpp if (n <= 0 || k <= 0 || k > n) { std::cerr << "Invalid input values." << std::endl; return 1; } ``` - **边界情况处理**：当 `n` 非常大时，排序操作可能会消耗大量的时间和内存，可以考虑使用更高效的算法来寻找第 `k` 大（小）的元素，例如快速选择算法，其平均时间复杂度可以达到 $O(n)$。 ### 📚相关学习资源 - **C++ 官方教程**：https://en.cppreference.com/w/ ，该网站提供了 C++ 标准库的详细文档，包括 `std::sort` 等函数的使用方法和示例。 - **《C++ Primer》**：一本经典的 C++ 入门和进阶书籍，涵盖了 C++ 语言的各个方面，适合初学者和有一定基础的开发者阅读。 ######[AI写代码神器 | 738点数解答 | 2026-08-24 19:58:19]