首页 > 代码库 > 选择问题(线性时间复杂度)
选择问题(线性时间复杂度)
采用分治策略找出第K小的元素!要求程序的时间复杂度为线性函数。
#include<iostream> #include<iterator> #include<algorithm> #include<time.h> #include<vector> using namespace std; /* *选择问题(线性时间复杂度) *在beg和end之间查找第k个元素 */ int Fast_find(vector<int> &vec,int beg,int end,int k) { if(k>end||k<beg+1) throw range_error("输入的参数错误"); if(beg+1>=end) { return vec[beg]; } int i ,j; for (i = beg,j = end; i < j; ) { do { j--; } while (vec[j]>vec[beg]); do { i++; }while(i<end&&vec[i]<vec[beg]); if(i<j) swap(vec[i],vec[j]); } swap(vec[beg],vec[j]); if(j==k-1) return vec[j]; if(j>k-1) return Fast_find(vec,beg,j,k); if(j<k-1) return Fast_find(vec,j+1,end,k); } int main() { vector<int> vec; copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(vec)); cin.clear(); int k ; cout<<"输入查找第几个元素(从小到大)!"<<endl; cin>>k; long start, end; int res; start = clock(); try { res = Fast_find(vec,0,vec.size(),k); } catch(range_error ex) { cout<<ex.what()<<endl; return 0; } end = clock(); cout<<"第"<<k<<"个元素"<<res<<endl; cout<<"验证!"<<endl; sort(vec.begin(),vec.end()); cout<<"第"<<k<<"个元素"<<vec[k-1]<<endl; cout <<"程序运行时间(单位:毫秒): "<< end-start <<endl; return 0; }
选择问题(线性时间复杂度)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。