找出一段数中的第Ｋ最大的数:k_Max

2019-11-10 17:04:19

字体：大中小

来源：转载

供稿：网友

先上代码：（时间复杂度后面分析＞＿＜）

#include<iostream>

#include<stdio.h>#include<stdlib.h>#include<time.h>using namespace std;void exchange(int *a,int *b){ if(a!=b) { int t=*a; *a=*b; *b=t; }}int partition(int *a,int left,int right){int x=a[right];int i=left-1;int j=left;for(;j<right;++j) { if(a[j]>=x) { ++i; exchange(&a[i],&a[j]); } } exchange(&a[i+1],&a[right]); return i+1;}int randomized_partition(int *a,int left,int right){srand((int)time(0));int i=rand()%(right-left+1)+left;if(i!=right)exchange(&a[i],&a[right]);return partition(a,left,right);}int Randomized_Select(int *a,int left,int right,int k){if(left==right) return a[left];int q=randomized_partition(a,left,right);int key=q-left+1;if(key==k)return a[q];else if(k<key)return Randomized_Select(a,left,q-1,k);elsereturn Randomized_Select(a,q+1,right,k-key);}int main(){int a[10]={1,9,2,8,10,3,4,7,6,5};int k;cin>>k;int k_max=Randomized_Select(a,0,9,k);cout<<k<<" Max: "<<k_max<<endl;return 0;}

期望为线性时间的选择算法

时间复杂度：

上一篇：最大子段和

下一篇：Leetcode 321 - Create Maximum Number（贪心）