C++求解数组前3个最小值的两种高效实现方案

## 💡 解题思路分析 本题要求从n个数字中找出前3个最小的值，并从小到大输出。由于n的范围较小（3≤n<100），且每个数范围在0~10000，可以采用**多种方法**实现。 ### 🔧 方法一：排序法（最直接） **将数组升序排序，输出前3个元素。** **优点**：实现简单，代码可读性高。 **缺点**：当n很大时排序开销高（本题n<100，可忽略）。 ### ⚡ 方法二：部分选择法（更高效） **只维护前3个最小值，无需完整排序。** **核心思想**：遍历数组，用3个变量记录当前最小的3个数，类似“打擂台”。 ```cpp int a, b, c; // a最小，b次之，c第三小 初始化a=b=c=INF; 遍历每个数x: if (x < a) { c=b; b=a; a=x; } else if (x < b) { c=b; b=x; } else if (x < c) { c=x; } ``` **优点**：时间复杂度O(n)，空间O(1)。 **缺点**：逻辑稍复杂，需注意边界（重复数字时用>=处理）。 --- ## ✅ 完整C++代码（排序法） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } // 升序排序 sort(nums.begin(), nums.end()); // 输出前3个 cout << nums[0] << " " << nums[1] << " " << nums[2] << endl; return 0; } ``` --- ## 📊 方法二：部分选择法（高效版）代码 ```cpp #include <iostream> #include <climits> using namespace std; int main() { int n, x; cin >> n; int min1 = INT_MAX, min2 = INT_MAX, min3 = INT_MAX; for (int i = 0; i < n; i++) { cin >> x; // 依次比较更新 if (x < min1) { min3 = min2; min2 = min1; min1 = x; } else if (x < min2) { min3 = min2; min2 = x; } else if (x < min3) { min3 = x; } } cout << min1 << " " << min2 << " " << min3 << endl; return 0; } ``` --- ## ⚠️ 注意事项与边界情况 | 情况 | 说明 | |------|------| | **存在重复数字** | 如输入 `2 2 3`，应输出 `2 2 3`。上述代码用`<`而非`<=`，能正确处理重复值。 | | **输入数据范围** | 数值在0~10000，`INT_MAX`足以表示无穷大。 | | **n≥3保证** | 题目已保证，无需额外判断。 | --- ## 🛠️ 开发建议 1. **优先选择排序法**：对于本题规模（n<100），排序法代码更简洁、不易出错。 2. **理解部分选择法**：该思想可扩展为“求前k个最小/最大”问题，在处理大数据时非常实用。 3. **注重边界测试**：建议测试用例包含重复数字、顺序乱序、全相同数字等情况。 4. **编码规范**：使用有意义的变量名（如`min1,min2,min3`），提高可读性。 5. **扩展思考**：如果n极大（如10^7），排序法可能超时，应使用堆（priority_queue）或快速选择算法。 --- ######[AI写代码神器 | 901点数解答 | 2026-08-09 10:46:43]