分治法之线性选择第i小元素

2019-11-06 07:15:50

字体：大中小

来源：转载

供稿：网友

#include<iostream>using namespace std;void swap(int& a,int& b) { if(a!=b) { a^=b; b^=a; a^=b; } }int PARTITION(int a[], int p ,int r){ int left = p,right = r,pivot = a[r]; while(left<right) { swap(a[left],a[right]); while(right>left&&a[right]>pivot)right--; while(left<right&&a[left]<=pivot)left++; } swap(a[left],a[p]); return left;}int select(int a[], int p ,int r, int i){ if(p == r) return a[p]; int q = PARTITION(a,p,r); int k = q-p+1; if(k == i) return a[q]; else if(i<k){ return select(a,p,q-1,i); }else{ return select(a,q+1,r,i-k); }}int main(){ int a[11] = {11,233,13,32,3,22,65464,-1,-43,21221,4}; PRintf("%d /n",select(a,0,10,5));}

上一篇：acdrem1083 人民城管爱人民 DP

下一篇：跑表精确至0.1秒