思路
使用快排思路就可以了,首先我们来回顾一下快速排序,这是一个典型的分治算法。我们对数组 做快速排序的过程是:
- 分解: 将数组 「划分」成两个子数组 、,使得 中的每个元素小于等于 ,且 小于等于 中的每个元素。其中,计算下标 q 也是「划分」过程的一部分。
- 解决: 通过递归调用快速排序,对子数组 和 进行排序。
- 合并: 因为子数组都是原址排序的,所以不需要进行合并操作, 已经有序。
由此可以发现每次经过「划分」操作后,我们一定可以确定一个元素的最终位置,即 x 的最终位置为 q,并且保证 a[l⋯q−1] 中的每个元素小于等于 a[q],且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。所以只要某次划分的 q 为第 k 个下标的时候,我们就已经找到了答案。 我们只关心这一点,至于 a[l⋯q−1] 和 a[q+1⋯r] 是否是有序的,我们不关心。
#include <iostream> #include <vector> using namespace std; int partition(vector<int> &nums, int low, int high){ int pivot = nums[low]; while (low < high){ while (nums[high] >= pivot && high > low) high--; nums[low] = nums[high]; while (nums[low] <= pivot && high > low) low++; nums[high] = nums[low]; } nums[low] = pivot; return low; } int findKthLargest(vector<int> &nums, int k){ int l = 0, r = nums.size() - 1; while (1){ int idx = partition(nums, l, r); if (idx == k) return nums[idx]; else if (idx > k) r = idx - 1; else l = idx + 1; } return 0; } int main(){ int n; while (cin >> n){ if (n == 0) break; vector<int> nums(n, 0); for (int i = 0; i < n; i++) cin >> nums[i]; if (n % 2) cout << findKthLargest(nums, n / 2) << endl; else cout << (findKthLargest(nums, n / 2 - 1) + findKthLargest(nums, n / 2)) / 2 << endl; } return 0; }