从无序（互异）数组中找到第K大的数

1.利用排序算法对其排序，然后直接取出第K个元素——O（nlogn）

随机选择算法——可达到O(N)级别

• 在对A[left,right]执行一次randpartition()后，主元A[p]左侧元素都小于主元，主元右侧元素都大于主元，且主元A[p]是第p-letf+1大的元素。当p>K时，在A[left,p-1]找第K大元素，、；当p==K时，找到；当p

#include
#include
#include
#include
#include
const int max=1000;
using namespace std;
double round(double r)//因为c++没有自带的round()四舍五入函数
{return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
}
int  randPartition(int(&a)[max],int low,int high){//这里数组大小需要标明//left,high内生成随机数p int p=(int)(round(1.0*rand()/RAND_MAX*(high-low)+low));//！！！ 取随机数太复杂啦！！swap(a[p],a[low]);//int t=a[low];while(low<high){while(low<high&&a[high]>t)high--; //= = ！！！千万别写成了a[high]>a[low] = =a[low]=a[high];while(low<high&&a[low]<=t) low++;a[high]=a[low];	}a[low]=t;return low;
}
int randSelect(int (&a)[max],int left,int right,int K){//!!除了引用外，**还可以设置全局变量**//递归边界if(left==right) return a[left]; int p=randPartition(a,left,right);int m=p-l+1;//下标所处的位置 if(K==m) return a[p];else if(K>p) return randSelect(a,p+1,right,K-m);else return randSelect(a,left,p-1,K);}
int main(){//生成随机数种子srand((unsigned)time(NULL)); int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}int K=3;printf("%d",randSelect(a,0,n-1,K));return 0;}

出自算法笔记

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！