解决排序找第三大数时间超限问题的两种方法

### ⏱️时间超限原因分析 #### 1. 排序算法复杂度高 代码中使用了冒泡排序算法来对数组进行排序，冒泡排序的时间复杂度是 $O(n^2)$，其中 $n$ 是数组的元素数量。当输入的 $n$ 比较大时，比如接近数据范围上限 50020 时，$n^2$ 的计算量会非常大，导致排序过程花费大量时间，从而容易出现时间超限的问题。 #### 2. 不必要的全排序 题目只需要找出第三大的数，而冒泡排序对整个数组进行了全排序，这会做很多不必要的操作。对于找出第 $k$ 大元素的问题，不需要将整个数组排序，可以使用更高效的算法，比如快速选择算法，其平均时间复杂度为 $O(n)$。 ### 💡解决方案 #### 方法一：使用 `std::sort` 库函数 C++ 标准库中的 `std::sort` 函数使用了优化的排序算法（如 IntroSort，结合了快速排序、堆排序和插入排序的优点），其平均时间复杂度为 $O(n log n)$，比冒泡排序更高效。 ```cpp #include <iostream> #include <algorithm> using namespace std; const int MAXN = 50020; long long n, a[MAXN]; int main() { scanf("%lld", &n); for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); } // 对数组进行排序 sort(a, a + n, greater<long long>()); // 去除重复元素 int uniqueIndex = 1; for (int i = 1; i < n; i++) { if (a[i] != a[i - 1]) { a[uniqueIndex++] = a[i]; } } // 确保有第三大的元素 if (uniqueIndex >= 3) { printf("%lld", a[2]); } return 0; } ``` #### 方法二：使用快速选择算法 快速选择算法可以在平均 $O(n)$ 的时间复杂度内找出第 $k$ 大的元素。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 快速选择函数 long long quickSelect(vector<long long>& nums, int left, int right, int k) { if (left == right) return nums[left]; int pivotIndex = left + rand() % (right - left + 1); pivotIndex = partition(nums, left, right, pivotIndex); if (k == pivotIndex) return nums[k]; else if (k < pivotIndex) return quickSelect(nums, left, pivotIndex - 1, k); else return quickSelect(nums, pivotIndex + 1, right, k); } // 分区函数 int partition(vector<long long>& nums, int left, int right, int pivotIndex) { long long pivot = nums[pivotIndex]; swap(nums[pivotIndex], nums[right]); int storeIndex = left; for (int i = left; i < right; i++) { if (nums[i] > pivot) { swap(nums[storeIndex], nums[i]); storeIndex++; } } swap(nums[storeIndex], nums[right]); return storeIndex; } int main() { int n; cin >> n; vector<long long> nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } // 去重 sort(nums.begin(), nums.end(), greater<long long>()); int uniqueIndex = 1; for (int i = 1; i < n; i++) { if (nums[i] != nums[i - 1]) { nums[uniqueIndex++] = nums[i]; } } nums.resize(uniqueIndex); // 确保有第三大的元素 if (uniqueIndex >= 3) { cout << quickSelect(nums, 0, nums.size() - 1, 2) << endl; } return 0; } ``` ### 💬代码解释 1. **`std::sort` 方法**：使用 `std::sort` 对数组进行降序排序，然后遍历数组去除重复元素，最后输出第三大的元素。 2. **快速选择方法**：首先对数组进行降序排序并去重，然后使用快速选择算法找出第三大的元素。快速选择算法通过分区操作不断缩小查找范围，最终找到第 $k$ 大的元素。 ######[AI问答 | 1124点数解答 | 2026-08-03 21:51:17]