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

### 🌟思路分析 要找到序列中第 `k` 大的元素和第 `k` 小的元素，我们可以先对序列进行排序，然后根据排序后的数组索引来获取所需的元素。具体步骤如下： 1. 读取输入的 `n` 和 `k`。 2. 读取 `n` 个正整数并存储在数组中。 3. 对数组进行排序。 4. 输出第 `k` 小的元素（排序后数组的第 `k - 1` 个元素）和第 `k` 大的元素（排序后数组的第 `n - k` 个元素）。 ### 💻代码实现 ```cpp #include <iostream> #include <algorithm> using namespace std; int main() { int n, k; // 读取 n 和 k cin >> n >> k; int a[1000]; // 读取 n 个正整数 for (int i = 0; i < n; i++) { cin >> a[i]; } // 对数组进行排序 sort(a, a + n); // 输出第 k 小的元素和第 k 大的元素 cout << a[n - k] << " " << a[k - 1] << endl; return 0; } ``` ### 🔍代码解释 1. **输入读取**：使用 `cin` 读取 `n` 和 `k`，然后使用循环读取 `n` 个正整数并存储在数组 `a` 中。 2. **排序**：使用 `sort` 函数对数组 `a` 进行排序。`sort` 函数是 C++ 标准库中的排序函数，它可以对数组进行升序排序。 3. **输出结果**：根据排序后的数组，第 `k` 小的元素是 `a[k - 1]`，第 `k` 大的元素是 `a[n - k]`，将它们输出。 ### 🚀进阶使用指南 - **性能优化**：如果 `n` 非常大，排序的时间复杂度为 $O(n log n)$。可以使用快速选择算法来优化，其平均时间复杂度为 $O(n)$。 - **错误处理**：需要考虑输入的 `k` 是否合法，即 `1 <= k <= n`。如果 `k` 不合法，需要给出相应的错误提示。 - **扩展功能**：可以将代码封装成函数，方便在其他程序中调用。 ### 📚学习资源 - [C++ 官方文档](https://en.cppreference.com/w/) - 《C++ Primer》 ### 💡开发建议 - 在编写代码前，先明确问题的需求和边界条件，避免出现错误。 - 对输入进行合法性检查，提高代码的健壮性。 - 可以使用注释来解释代码的功能和逻辑，提高代码的可读性。 ######[AI写代码神器 | 688点数解答 | 2026-04-17 20:07:47]