2110 - 求第k大数
<span style="font-weight:bold;font-size:16pt;font-family:'Courier New';">求第k大的数</span>
<span style="font-weight:bold;font-size:10.5pt;font-family:'Courier New';">(Kth.pas/c/cpp)</span><span style="font-family:'sans serif', tahoma, verdana, helvetica;font-size:12px;line-height:1.5;"></span>
<br />
给定一个长度为n（1≤n<span>≤1,000,000）的无序正整数序列，以及另一个数k（1<span>≤k<span>≤1,000,000</span></span>）（关于第k大的数：例如序列{1,2,3,4,5,6}中第3大的数是4。）</span>
Input
第一行两个正整数m,n。
第二行为n个正整数。
Output
第k大的数。
Examples
Input
6 3 1 2 3 4 5 6
Output
4
Solution C
#include<stdio.h> int main(){ int amount,k,i; scanf("%d%d",&amount,&k); int a[amount],left[amount],right[amount]; for(i=0;i<amount;i++) scanf("%d",&a[i]); printf("%d",search(a,k,amount)); } int search(int b[],int kk,int amountb){ int left[amountb],right[amountb]; int i,numl=0; int numr=0; for (i=1;i<amountb;i++){ if(b[i]<=b[0]){left[numl]=b[i];numl++;} if(b[i]>b[0]){right[numr]=b[i];numr++;} } if(numr>(kk-1))return search(right,kk,numr); if(numr<(kk-1))return search(left,kk-numr-1,numl); else return b[0]; }
Solution C++
#include<iostream> #include<cstring> #include<string> #include<cstdlib> #include<algorithm> using namespace std; int main(){ int n,k,t=1;cin>>n>>k; int a[n+1],ans[n+1]; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); ans[1]=a[1]; for(int i=2;i<=n;i++) if(a[i]!=ans[t]){ ans[t+1]=a[i]; t++; } if(k>t) {cout<<"NO RESULT";return 0;} else cout<<ans[n-k+1]; return 0; }