C++实现查找序列中第k大与第k小元素

### 🍭问题分析 要找到序列中第 `k` 大的元素和第 `k` 小的元素，我们可以先对序列进行排序，然后根据排序后的结果直接获取第 `k` 大（从后往前数第 `k` 个）和第 `k` 小（从前往后数第 `k` 个）的元素。 ### 💻代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> 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 小的元素 int kthSmallest = a[k - 1]; // 第 k 大的元素 int kthLargest = a[n - k]; // 输出结果 std::cout << kthLargest << " " << kthSmallest << std::endl; return 0; } ``` ### 📝代码解释 1. **输入读取**：首先读取 `n` 和 `k`，然后读取 `n` 个正整数存储在 `vector` 中。 2. **排序**：使用 `std::sort` 函数对 `vector` 进行排序，默认是升序排序。 3. **获取第 `k` 小和第 `k` 大的元素**：排序后，第 `k` 小的元素是 `a[k - 1]`，第 `k` 大的元素是 `a[n - k]`。 4. **输出结果**：将第 `k` 大的元素和第 `k` 小的元素输出，中间用空格分隔。 ### 🚀开发建议 - **错误处理**：可以添加输入验证，确保 `k` 的值在合法范围内（`1 <= k <= n`），避免出现越界错误。 - **性能优化**：如果 `n` 非常大，排序的时间复杂度是 $O(n log n)$，可以使用快速选择算法，将时间复杂度优化到 $O(n)$。 ### 📚学习资源 - [C++ 官方文档](https://en.cppreference.com/w/)：提供了 C++ 标准库的详细文档和示例。 - 《C++ Primer》：一本经典的 C++ 学习书籍，适合初学者和有一定基础的开发者。 ######[AI写代码神器 | 625点数解答 | 2026-05-24 16:01:05]