C++实现数组第二小值查找算法及代码解析

好的，这个问题很直接。根据你的描述，我们需要在数组中找出第二小的值，而且算法已经给出了明确的步骤：先找最小值放到第一位，再在剩下的元素中找最小值，这个就是第二小的值。 下面我为你提供一个清晰的 **C++** 解决方案，并附上详细解释。 ## 🧠 解题思路 根据提示，我们可以使用 **选择排序** 的部分过程： 1. 遍历整个数组，找到最小的元素，并与 `a[1]`（即第一个元素）交换。 2. 再次遍历从第二个元素开始的剩余部分，找到最小的元素，这个就是整个数组的第二小的值。 3. 直接输出 `a[2]`（索引为 1）。 **为什么这样有效？** 因为第一次找最小值放到最前面后，第二次找最小值时，会忽略掉已经放好的第一个最小值，从剩下的元素中找最小，那自然就是全局第二小的值。 ## 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int a[100]; // 根据题目 n < 100 for (int i = 0; i < n; i++) { cin >> a[i]; } // 第一步：找最小值，与 a[0] 交换 int minIndex = 0; for (int i = 1; i < n; i++) { if (a[i] < a[minIndex]) { minIndex = i; } } // 交换 a[0] 和 a[minIndex] int temp = a[0]; a[0] = a[minIndex]; a[minIndex] = temp; // 第二步：从 a[1] 开始找最小值，就是第二小的值 minIndex = 1; for (int i = 2; i < n; i++) { if (a[i] < a[minIndex]) { minIndex = i; } } // 交换 a[1] 和 a[minIndex]（其实不交换也能输出 a[1] 的值，但为了符合题目描述，可以交换） temp = a[1]; a[1] = a[minIndex]; a[minIndex] = temp; // 输出第二小的值 cout << a[1] << endl; return 0; } ``` ## 📝 代码详解 - **第一趟找最小值**： - `minIndex` 初始为 `0`，遍历数组，如果发现更小的元素，就更新下标。 - 找到后与 `a[0]` 交换，确保最小值在第一位。 - **第二趟找次小值**： - 从 `a[1]` 开始（因为第一个已经是最小值了），遍历到末尾，找到最小的元素。 - 该元素的值即为整个数组第二小的值。 - **输出**：直接输出 `a[1]` 的值（交换后，`a[1]` 就是第二小的值）。 ## 🧪 测试样例验证 **输入：** ``` 5 4 3 5 2 6 ``` **执行过程：** 1. 第一趟：最小值是 `2`，在索引 `3`，与 `a[0]=4` 交换 → 数组变为 `{2, 3, 5, 4, 6}` 2. 第二趟：从 `a[1]` 开始找最小，`a[1]=3`，`a[3]=4`，`a[4]=6`，`a[2]=5`，最小值是 `3`，它与 `a[1]` 本来就是 `3`，不变。 3. 输出 `a[1] = 3`，正确。 **输出：** ``` 3 ``` ## ⚠️ 注意事项和开发建议 - **数组大小**：题目限定 `n < 100`，所以定义 `a[100]` 足够，但为了更安全，可以用 `vector` 动态分配。 - **时间复杂度**：这里做了两次遍历，时间复杂度为 O(n)，对于 n<100 是完全可以接受的。 - **重复值处理**：如果数组中有重复的最小值，例如 `{1, 1, 2}`，第一趟找到最小值 `1` 放到第一位，第二趟从 `a[1]` 开始，此时 `a[1]` 也是 `1`，那么第二小的值也是 `1`，这是合理的，因为有两个相同的最小值。 - **边界情况**：当 `n < 2` 时，没有第二小的值，但题目没有给出这种情况，一般默认 n ≥ 2。 ## 📚 拓展思考 你可以尝试用其他方法实现，例如： - 直接遍历两次，记录最小值和次小值（不使用交换）。 - 使用 `std::nth_element` 或 `std::partial_sort` 等 STL 函数，但那样可能略复杂，且对于这个简单问题不必要。 如果你希望用更简洁的方式，可以直接在一次遍历中同时记录最小值和次小值，但题目要求用交换的方式，我们就按题意实现，这样更符合评测要求。 --- ######[AI写代码神器 | 1159点数解答 | 2026-08-08 11:23:28]