1235：输出前k大的数

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

10
4 5 6 9 8 7 1 2 3 0
5

【输出样例】

9
8
7
6
5

解析：排序后输出前k个数，时间复杂度为O(NlogN)，太简单了，略；

正解是使用分治的思路来解决，我们可以使用快速排序的思路，利用一个中间值，将数组分成两部分，前半部分大于中间值，后一部分小于中间值；

然后对这两部分递归调用快速排序；

 重点：对于不包含1-k的区间，可以忽略，这样就可以使时间复杂度降低到O(N)

详见代码：

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int n, k;
void qs(int l, int r) {//快速排序
    if(l >= r)
        return;
    int i = l, j = r;
    int mid = a[(l + r) / 2]; //将当前序列在中间位置的数定义为分隔数
    while(i <= j) { //注意这里不能少了等号
        while(a[i] > mid)
            i++;  //在左半部分寻找小于等于中间数的数
        while(a[j] < mid)
            j--;    //在右半部分寻找大于等于中间数的数
        if(i <= j) { //若找到一组与排序目标不一致的数对
            swap(a[i], a[j]);//则交换它们
            i++;
            j--;
        }
    }
    qs(l, j);//递归快排左右区间
    if (i <= k) { //对于超过k的区间，不用再处理了
        qs(i, r);
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a[i]);
    }
    scanf("%d", &k);
    qs(1, n);
    for(int i = 1; i <= k; ++i){
        printf("%d\n", a[i]);
    }
    return 0;
}