中位数

思路

使用快排思路就可以了，首先我们来回顾一下快速排序，这是一个典型的分治算法。我们对数组 做快速排序的过程是：

• 分解： 将数组 「划分」成两个子数组 、，使得 中的每个元素小于等于 ，且 小于等于 中的每个元素。其中，计算下标 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;
}