学步园

   编程之美上的寻找N个数中最大的前K数，给出了一种算法，我认为比较好：
  算法是这样写的：

   假设N个数存储在数组S中，我们从数组S中随机选出一个元素X，把数组分为两部分Sa和Sb.Sa中的元素都大于X，Sb中的元素都小于X，这时，有两种可能性：
1.Sa中元素的个数小于K，Sa中所有的数和Sb中最大的K-|Sa|个数（|Sa|指Sa中元素的个数）就是数组S中最大的K个数。
2.Sa中元素的个数大于或等于Ｋ，则直接返回Sa中最大的K个元素。

平均时间复杂度O(N*log2 K)

伪代码

Kbig(S,K)<br /> if(k<=0):<br /> return []<br /> if(length S<=K):<br /> return S<br /> (Sa,Sb)=Partition(s)<br /> return Kbig(Sa,k).Append(Kbig(Sb,k-length Sa)<br /> //////////////////////////////////////////////////<br /> Partition(S):<br /> Sa=[];<br /> Sb=[];<br /> Swap(s[1],S[random()%length S])<br /> p=S[1]<br /> for i in [2:length S]:<br /> s[i] > p ? Sa.Append(s[i]):Sb.Append(S[i])</p> <p>length Sa<length Sb ? Sa.Append(p):Sb.Append(p)<br /> return (Sa,Sb)<br />

我的实现

#include <stdio.h><br /> #include <tchar.h><br /> #include <iostream><br /> #include <vector><br /> #include <stdlib.h><br /> #include <time.h><br /> using namespace std;<br /> vector<int> Kbig(vector<int>&,int);<br /> pair<vector<int>,vector<int> > Partition(vector<int>);<br /> int main()<br /> {<br /> vector<int> origin(10000,0);<br /> int k;<br /> cout <<"origin array:"<<endl;<br /> for (int i = 0;i < 10000;i++)<br /> {<br /> origin[i] = rand() % 10001;<br /> cout << origin[i] << " ";<br /> }<br /> cout << endl;</p> <p> cout << "请输入你想找的最大的数的个数："<<endl;<br /> cin >> k;<br /> origin = Kbig(origin,k);</p> <p> cout << "最大的" << k << "个数是："<< endl;<br /> for(vector<int>::iterator iter = origin.begin();iter != origin.end(); ++iter )<br /> cout << *iter <<" ";<br /> cout << endl;</p> <p> return 0;<br /> }</p> <p>vector<int> Kbig(vector<int>& origin,int k)<br /> {<br /> pair<vector<int>,vector<int> > ret;<br /> vector<int> sa,sb,temp;<br /> if(k <= 0)<br /> return origin;<br /> if(origin.size() <= k)<br /> return origin;<br /> ret = Partition(origin);<br /> sa = ret.first;<br /> sb = ret.second;<br /> if (sa.size() >= k)<br /> {<br /> return Kbig(sa,k);<br /> }<br /> else<br /> {<br /> temp = Kbig(sb,k - sa.size());<br /> for (vector<int>::iterator iter = temp.begin(); iter != temp.end();++ iter)<br /> {<br /> sa.push_back(*iter);<br /> }<br /> return sa;<br /> }</p> <p>}</p> <p>pair<vector<int>,vector<int> > Partition(vector<int> origin)<br /> {<br /> srand((unsigned)time(NULL));<br /> vector<int> sa,sb;<br /> pair<vector<int>,vector<int> > ret;<br /> int p;<br /> swap(origin[0],origin[rand()%origin.size()]);<br /> p = origin[0];<br /> for (vector<int>::iterator iter = origin.begin() + 1;iter != origin.end();++iter)<br /> *iter > p ? sa.push_back(*iter) : sb.push_back(*iter);<br /> sa.size() < sb.size() ? sa.push_back(p) : sb.push_back(p);<br /> ret = make_pair(sa,sb);<br /> return ret;<br /> }