寻找在数组中最大的K个数

问题描述：

   有一个长度为N的无序数组，假定其中的每一个元素都各不相等，求其中最大的K个数。 

思路一：快速排序或者是堆排序

   bool Kbig(int * array,int n,int k,int * karray)

   {

           //数组元素从1到n

           quickSort(array,1,n);//进行快速排序

           for i in [1 : k]:

                karray[i] = array[i]

   }

   时间复杂度分析：快速排序和堆排序的时间复杂度都是O(nlog n/2),取出前k个的时间复杂度是O(K),总的时间复杂度是：O(nlog n/2) + O(K) = O(nlog n/2)

   缺点：需要将N个数一次性的导入内存，当N很大的时候，方案变的不现实，另外当K很小的时候，依然需要对N-K个元素进行排序，这是不需要的。

思路二：选择排序

   避免对N-K个元素进行排序，只是对前K个元素进行排序，时间复杂度是O(N * K)，K的大小对于算法的选取是起决定性的作用的。

思路三：

   参考快速排序中的一次划分的算法

   假设N个数存储在数组S中，我们从数组S中随机的找到一个元素X，把数组分成两部分Sa和Sb。Sa中的元素大于等于X，Sb中的元素小于X。

   这是有两种可能性

   (1)Sa中的元素个数小于K，Sa中所有的数和Sb中最大的K-|Sa|个元素就是数组S中最大的K个数。

   (2)Sa中的元素的个数大于等于K，则需要返回Sa中最大的K个元素。

   

Kbig(S,k)
{
     if(k <= 0)
          return [];
     if(length S <= k):
          return S;
     (Sa,Sb) = Partition(S);
      return Kbig(Sa,k).Append(Kbig(Sb,k - Sa.length))
}
Partion(S):
   Sa = []
   Sb = []
   Swap(S[1],S[Random()%S.length])
   p = S[1]
   for i in [2:S.length]:
       S[i] > p ? Sa.Append(S[i]):Sb.Append[S[i]]
   Sa.Sppend(p);
   return(Sa,Sb)

平均的时间复杂度分析：

        T(K) = 2T(K/2) + O(1) 

Partion(S)的时间复杂度是O(N)

所以总的时间复杂度是O(N * log N /2)

     

例子： 

  S = 9，8，6,4,7,3,2,1,5  K = 3

   首先第一个元素X = 3

   Sa = 9,8,6,4,7,5,3

   Sb = 2,1

   因为|Sa| > 3,需要返回Sa中最大的3个元素，将Sa分成两部分Sa1和Sb1,第一次递归，调用Kbig(Sa1,K).Append(Kbig(Sb1,K - Sa1.length)),K - Sa1.length有可能是负数，将会导致该分支的终结。具体调用：Kbig(Sa,3)继续 Kbig(Sb,3 - 7)结束

   S = 9,8,6,4,7,5,3   X = 4

   Sa = 9,8,6,7,5,4  

   Sb = 3 

   因为|Sa| > 3,需要返回Sa中最大的3个元素，第二次递归。具体调用：Kbig(Sa,3)继续 Kbig(Sb,3 - 6)结束

   S = 9,8,6,7,5,4   X = 8

   Sa = 9,8

   Sb = 6,7，5,4

   因为|Sa| < 3,所以直接返回Sa中的全部的元素，然后调用Kbig(Sb,3 - 2))

   S = 6,7，5,4    X = 7

   Sa = 7

   Sb = 6,5,4

   因为|Sa| <= 1,所以直接返回Sa中的全部的元素，然后调用Kbig(Sb,1 - 3))结束

所以程序最终的返回结果是9,8,7

解法四：二分搜索

寻找N个数中最大的K个数，本质上就是寻找最大的K个数中的最小的，也就是第K大的数。可以使用二分搜索的方法。

    

while(Vmax - Vmin > delta)
{
   Vmid = Vmin + (Vmax - Vmin) * 0.5；
   if(f(S,N,Vmid) >= K)
        Vmin = Vmid;
   else
        Vmax = Vmid;
}


函数  f(S,N,Vmid）中返回的是S[1....N]中大于等于Vmid的数的个数

上述代码中delta的取值要比S中任意两个不相等的元素的差值的最小值小

循环运行之后，得到一个区间(Vmin,Vmax).这个区间只包含一个元素或者多个相等的元素。这个元素就是第K大元素。

时间复杂度是O(N * log N/ 2)

  例子：

      S = 1，2，3,4,11   K = 3

     初始：Vmax = 11 Vmin = 1

     Vmid = (1 + 11) / 2 f(S,9,6) = 1 < K 因此Vmax =  Vmid
     Vmid = (1 + 6) /2  f(S,9,3.5) = 2 < K  因此Vmax =  Vmid 
     Vmid = (1 + 3.5) /2  f(S,9,2.25) = 3 = K  因此 Vmin =  Vmid 
     Vmid = (2.25 + 3.5) /2  f(S,9,2.875) = 3 = K  因此 Vmin =  Vmid 

     Vmid = (2.875 + 3.5) /2  f(S,9,3.1875) = 2 < K  因此 Vmax =  Vmid 

     因为(3.1875 - 2.875) < 0.5 因此第K大的数是 Vmin < 3 < Vmax 

方法五：K堆排序

    构造K个元素的小顶堆来存储最大的K个数。最小堆的堆顶(Y)就是最大的K个数中的最小的一个。对于每一个新的数X，如果X < Y,则不需要更新堆。如果X>Y,那么用X替换掉堆顶的元素Y，然后调整小顶堆结构。

    只需要扫面一次所有数据，时间复杂度是O(N * log K / 2)

解法六：计数排序

    计数排序：适用的范围是N个数的范围不是太大，可以考虑申请空间，记录每一个整数的出现的次数，然后再从大到小取最大的K个。

     时间复杂度O(N),空间复杂度O(N)