运行超时还可以理解,优化也也知道,左边的一些数不需要继续递归,但是不知道怎么写,答案错误不能理解,我觉得我写得挺对的啊,本身又不难,请指教,谢谢
【题目描述】 给定一个数组,统计前k大的数并且把这k个数从大到小输出。
【输入】 第一行包含一个整数n,表示数组的大小。n < 100000。
第二行包含n个整数,表示数组的元素,整数之间以一个空格分开。每个整数的绝对值不超过100000000。
第三行包含一个整数k,k < n。
【输出】 从大到小输出前k大的数,每个数一行。
【输入样例】 10 4 5 6 9 8 7 1 2 3 0 5 【输出样例】 9 8 7 6 5
//输出前k大的数
#include<bits/stdc++.h>
using namespace std;
int n,i,j,a[100010];
void binary_Search(int l,int r);
int main()
{
cin>>j;
for(int o=1;o<=j;o++) cin>>a[o];
cin>>i;
binary_Search(1,j);
for(int o=j;o>=j-i+1;o--)
{
cout<<a[o]<<endl;
}
return 0;
}
void binary_Search(int l,int r)
{
int k=l,q=r,s;
s=(l+r)/2;
while(k<=q)
{
while(a[k]<a[s]) k++;
while(a[q]>a[s]) q--;
if(k<=q)
{
swap(a[k],a[q]);
k++; q--;
}
}
if(l<q) binary_Search(l,q);
if(r>k) binary_Search(k,r);
}