整数数组中第三大元素查找代码的问题分析与修正

### ⏱️时间超限原因 这段代码使用冒泡排序对数组进行排序，冒泡排序的时间复杂度为 $O(n^2)$。在本题中，对于 $100\%$ 的数据，$n$ 最大可达 $50000$，当 $n$ 接近这个上限时，$n^2$ 会是一个非常大的数字，使得程序的运行时间显著增加，进而导致时间超限。 代码逻辑存在问题，排序后数组是升序的，直接输出 `a[3]` 得到的是第三小的数，而不是第三大的数。 ### ✅修正后的代码 ```cpp #include <cstdio> const int N = 50010; // 修正数组大小以适应题目数据范围 int n, a[N], x; int main() { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } // 冒泡排序 for(int i = 0; i < n - 1; i++) { for(int j = 0; j < n - i - 1; j++) { if(a[j] < a[j + 1]) { // 改为降序排序 x = a[j]; a[j] = a[j + 1]; a[j + 1] = x; } } } // 输出第三大的数 printf("%d", a[2]); return 0; } ``` ### 📝修改说明 1. **数组大小**：将数组 `a` 的大小从 `N = 1e2 + 10` （即 110）修改为 `N = 50010`，以满足题目中 $3 \leq n \leq 50000$ 的数据范围要求。 2. **排序顺序**：将冒泡排序的比较条件从 `a[j] > a[j + 1]` 改为 `a[j] < a[j + 1]`，让数组按降序排列。这样排序后，`a[2]` 就是第三大的数。 3. **数组下标**：将数组的下标从从 1 开始改为从 0 开始，符合 C++ 数组的常规使用习惯。 尽管这样修改能修正逻辑问题，但使用冒泡排序在 $n$ 较大时仍然效率较低，更好的做法是使用 C++ 标准库的 `std::sort` 函数，其平均时间复杂度为 $O(n log n)$。 ######[AI问答 | 616点数解答 | 2026-08-04 22:53:29]