取n个数中第k大数
发布时间:2020-12-14 01:41:20 所属栏目:大数据 来源:网络整理
导读:问题:有一个大小为n的数组,求其中第k大的数。 这里采用快速排序思想,将数组进行划分 ,该算法时间复杂度为O(n)。 #includeiostream#includetime.h#includestdlib.husing namespace std;int random_partion(int *arry,int n){ time_t t; srand((unsigned)t
问题:有一个大小为n的数组,求其中第k大的数。 这里采用快速排序思想,将数组进行划分 ,该算法时间复杂度为O(n)。 #include<iostream> #include<time.h> #include<stdlib.h> using namespace std; int random_partion(int *arry,int n) { time_t t; srand((unsigned)time(&t)); int index=rand()%n; swap(arry[index],arry[n-1]); //起到随机效果 int i=-1; //i指向小于p[n-1]的元素的位置 int j=0; while(j<n) { //将大于p[n-1]的数交换到前半部分 if(arry[j]>arry[n-1]) { swap(arry[++i],arry[j]); } j++; } swap(arry[++i],arry[n-1]); return i; } int getKMax(int *arry,int n,int k) { int pos; if(k<=0) return -1; if(k>n) return -1; pos=random_partion(arry,n); //对原数组进行划分 if(pos == k-1) //如果pos+1==k,那么返回该值,这就是第k大的数 return arry[pos]; else if(pos<k-1) return getKMax(arry+pos+1,n-pos-1,k-pos-1); else return getKMax(arry,pos,k); } int main() { int arry[] = {543,56,6435,965,561,555,604,21,546,844,68}; int k; cout<<"input k:"; cin>>k; cout<<getKMax(arry,11,k)<<endl; system("pause"); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |