计算序列中第k小的数

作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4046399.html

使用分治算法，首先选择随机选择轴值pivot，并使的序列中比pivot小的数在pivot左边，比pivot大的数在pivot右边，即快速排序算法中的partition的过程，可以参考：快速排序算法 Quick sort。

进行partition过程后，我们随机选择的轴值为序列的第j个，且其左边有a个数，右边有b个数。

如果j=k，那么说明该轴值就是第k小个数。

如果j>k，说明第k小的数一定在轴值的左边，我们可以递归的查找左侧a个数中的第k大个数。

如果j<k，说明第k小的数一定在轴值的右侧，且其左侧的a+1个数都小于第k小的数，所以我们可以递归的查找右侧b个数中的第k-a-1小的数。

由于每次规模缩小一半，且每次处理的时间为O(n)，那么我们可以得到其平均复杂度为:T(n)=T(n/2)+n

根据主定理我们可以得到算法的复杂度为O(n)

代码如下：

 #include <cstdio>

 #include <cstdlib>

 #include <iostream>

 #include  <vector>

 #include  <ctime>

 using namespace std;

 void swap(int &a, int &b)

 {

     int tmp = a;

     a = b;

     b = tmp;

 }

 int partation(vector<int> &vec, int begin, int end, int pivot)

 {

     swap(vec[pivot], vec[begin]);

     int tmp = vec[begin];

     int p = begin, q = end;

     while( p < q )

     {

         while( p < q && vec[q] >= tmp) q--;

         if( p < q ) vec[p++] = vec[q];

         while( p < q && vec[p] < tmp ) p++;

         if( p < q ) vec[q--] = vec[p];

     }

     vec[p] = tmp;

     return p;

 }

 int FindKMin(vector<int> & vec, int begin, int end, int k)

 {

     srand(time());

     int piovt = rand()%(end-begin+)+begin;

     int pos = partation(vec, begin, end, piovt);

     if( pos-begin+ ==  k )

     {

         return vec[pos];

     }

     else if( pos-begin+ > k )

     {

         return FindKMin(vec, begin, pos-, k);

     }

     else

     {

         return FindKMin(vec, pos+, end, k-(pos-begin+));

     }

 }

 int main(int argc, char *argv[])

 {

     int n;

     vector<int> vec;

     while( cin >> n )

     {

         vec.clear();

         int k;

         cin>>k;

         int tmp;

         for( int i =  ; i < n  ; i++ )

         {

             cin>>tmp;

             vec.push_back(tmp);

         }

         cout<<FindKMin(vec, , vec.size()-, k)<<endl;

     }

 }

该方法的最坏复杂度为$O(n^2)$，最坏情况是第一阶段每次选择的轴都为最大的数，并递归计算前n-1个数的第k小数，直到第k小数为这个序列的最大值为止。第二阶段每次选择的轴为最小的数，直到只剩下第k小数这一个数。那么该复杂度为$O(n^2)$。

我们可以使用另一种方法来替代随机选择轴值，并使得该算法的最坏情况的复杂度也为O(n)，选择轴值方法如下：

1. 将输入数组的n个元素划分为$\lfloor n/5 \rfloor$，每组5个元素，至多只有一组由剩下的nmod5个元素组成。

2. 寻找$\lceil n/5 \rceil$个组中每组的中位数，即对其进行排序，从而找到$\lceil n/5 \rceil$个中位数，并对这$\lceil n/5 \rceil$个中位数组成的数组继续递归调用找出其轴值。

使用该方法找到的轴值并不是数组真正的中位数。但是它具有一定的性质，在大于轴值的那些中位数的组且不包括最后个数少于5的那个组中，每组至少有3个数大于轴值。不计算这两个组，大于轴值的元素个数至少为：

\begin{equation} 3(\lceil \frac{1}{2}\lceil \frac{n}{5}\rceil\rceil -2) \geq \frac{3n}{10}-6 \end{equation}

从而时间复杂度为：$T(n) \leq T(\lceil n/5 \rceil ) + T(7n/10+6) + O(n) = O(n)$

选择轴值的代码，需要建立一个类unit来保存第i个数的值和其位置，并且最终返回轴值的位置。main函数包括了数组长度为4-6的数全排列的测试。

代码如下：

 #include <cstdio>

 #include <cstdlib>

 #include <iostream>

 #include  <vector>

 #include  <algorithm>

 using namespace std;

 class unit

 {

     public:

         int x, num;

         unit(int xx=, int nn=)

         {

             x = xx;

             num = nn;

         }

         bool operator < (const unit &a) const

         {

             return this->x < a.x;

         }

 };

 int getp(vector<unit> vec)

 {

     if( vec.size() <=  )

     {

         sort(vec.begin(), vec.end());

         return vec[vec.size()/].num;

     }

     vector<unit> small;

     unit tmp;

     for( int i =  ; i < vec.size()-vec.size()% ; i+= )//i is the start index in the team

     {

         sort(vec.begin()+i, vec.begin()+i+);

 //        for( int j = 0 ; j < 5 ; j++ )

 //        {

 //            cout<<vec[i+j].x<<" ";

 //        }

 //        cout<<endl;

         tmp.x = vec[i+].x;

         tmp.num = vec[i+].num;

         small.push_back(tmp);

     }

     int remain = vec.size()%;

     int teamnum = vec.size()/;

     if( remain !=  )

     {

         sort(vec.begin()+teamnum*, vec.end());

         tmp.x = vec[teamnum*+remain/].x;

         tmp.num = vec[teamnum*+remain/].num;

         small.push_back(tmp);

     }

 //    for( int i = 0 ; i < small.size() ; i++ )

 //    {

 //        cout<<small[i].x<<" ";

 //    }

 //    cout<<endl;

     return getp(small);

 }

 int getpivot(const vector<int> vec)

 {

     vector<unit> vecunit;

     unit tmp;

     for( int i =  ; i < vec.size() ; i++ )

     {

         tmp.x = vec[i];

         tmp.num = i;

         vecunit.push_back(tmp);

     }

     return getp(vecunit);

 }

 int main(int argc, char *argv[])

 {

    vector<int> a;

    for( int i =  ; i <  ; i++ )

    {

        a.clear();

        for( int j =  ; j < i ; j++ )

        {

             a.push_back(j);

        }

        cout<<endl;

        do{

             cout<<"array is ";

             for( int k =  ; k < a.size() ; k++ )

             {

                 cout<<a[k]<<" ";

             }

             cout<<endl;

            cout<<"result "<<getpivot(a)<<endl;

        }while(next_permutation(a.begin(), a.end()));

    }

 }

巴特西

计算序列中第k小的数

最新文章

热门文章