題目
原題地址
利用快排的思想，首先將前m的數(shù)移至數(shù)組右邊芬萍，然后用內(nèi)置sort函數(shù)對(duì)這m個(gè)數(shù)排序，最后輸出即可搔啊。
為什么不能直接全局sort柬祠，然后輸出m個(gè)數(shù)呢？因?yàn)檫@樣的題目數(shù)組特別大负芋，復(fù)雜度特別高漫蛔。這里我們運(yùn)用快排的思想找到前m大的數(shù)只花費(fèi)了的時(shí)間，另外排序花了
旧蛾，總復(fù)雜度為
莽龟，比
小很多。
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1000100
int A[maxn];
int n,m;
//將數(shù)組l到r位置前k大的數(shù)移到l到r位置的右邊
void move_right(int *A, int l, int r, int k){
if(l>r) return;
int i=l,j=r;
int key=A[l];
while(i!=j){
if(i<j&&A[j]>=key) --j;
swap(A[i],A[j]);
if(i<j&&A[i]<=key) ++i;
swap(A[i],A[j]);
}
int len = r-i+1;
if(len==k) return;
else if(len>k) move_right(A, i+1, r, k);
else move_right(A,l,i-1,k-len);
}
int main()
{
while(cin>>n>>m){
for(int i=0; i<n;i++) cin >> A[i];
//memset(A, 0, sizeof(A));
move_right(A,0,n-1,m);
sort(A+n-m,A+n); //將右邊的m個(gè)數(shù)升序排序
for(int i=n-1;i>=n-m;i--) cout << A[i] << " ";
}
return 0;
}
