Top k问题（线性时间选择算法）

问题描述：给定n个整数，求其中第k小的数。

分析：显然，对所有的数据进行排序，即很容易找到第k小的数。但是排序的时间复杂度较高，很难达到线性时间，哈希排序可以实现，但是需要另外的辅助空间。

这里我提供了一种方法，可以在O(n)线性时间内解决Top k问题。关于时间复杂度的证明，不再解释，读者可以查阅相关资料。具体的算法描述如下：

算法：LinearSelect(S,k)

输入：数组S[1:n]和正整数k，其中1<=k<=n；

输出：S中第k小的元素

1. If n<20 Then 将S中的元素排序后输出第k个元素，算法结束；

2.将S划分为无公共元素的 floor(n/5) 个分组，每组5个元素，第 i 个组记为Si；

3.用插入排序算法将每个组Si 排序，求得中位数 mi ，其中 i=1,2,3,...,floor(n/5)；

4.递归调用本算法求得｛mi | 1<=i floor(n/5)｝的中位数（即第floor(n/10)小的元素）M；

5.划分S为A=｛x|x属于S 并且 x<M｝， B=｛x|x属于S 并且 x=M｝和C=｛x|x属于S 并且 x>M｝；

6. If |A|>k Then 输出 LinearSelect(A,k)；

7. ElseIf |A|+|B|<k Then 输出 LinearSelect(C,k-|A|-|B|)；

8. Else 输出M，算法结束；

当然了，本题是求第k小，如果求第k大，可以转换成对应的第n-k小，同样可以求。这个算法以后会经常用到，一定要掌握，但是如果数据量不超过20个的话，也可以直接排序求。

完整的Java代码如下，代码写法都比较通用，读者可以很容易转换为其他语言实现：

 1 import java.lang.Math;
 2 import java.util.Arrays;
 3 import java.util.Scanner;
 4 public class Topk {
 5     public static int LinearSelect(int s[],int n,int k)
 6     {   int topk=0;
 7         if(n<=0)return topk;                          //如果数组为空，则返回0
 8         if(n<5)                                      //这里对应算法的第一步。这里我定义的是小于5个，则直接排序，读者也可以自己设定
 9         {     
10                for(int i=0;i<n-1;i++)
11                    for(int j=i+1;j<n;j++)
12                        if(s[i]>s[j])
13                        {int t=s[i];s[i]=s[j];s[j]=t;}
14              topk= s[k-1];
15         }
16        else{
17            
18         int ss[][]=new int[n/5][5];                  //对应算法的第二步
19         int j=-1;
20         for(int i=0;i<n/5*5;i++)
21         { if(i%5==0)j++;
22              ss[j][i%5]=s[i];
23             
24         } 
25         
26         int sss[]=new int[n/5];
27         for(int i=0;i<n/5;i++)                      //对应算法的第三步
28         { 
29             Arrays.sort(ss[i]);
30             sss[i]=ss[i][2];
31             
32         }
33         Arrays.sort(sss);
34         int M=sss[n/5/2];                           //对应算法的第四步
35         
36         int A[]=new int[n];                         //对应算法的第五步
37         int B[]=new int[n];
38         int C[]=new int[n];
39         int a=0,b=0,c=0;                      //作为三个结合的指针
40         for(int i=0;i<n;i++)                  //放入对应的集合中
41          {
42             if(s[i]<M)A[a++]=s[i];
43             if(s[i]==M)B[b++]=s[i];
44             if(s[i]>M)C[c++]=s[i];
45             }
46        
47         if(a>k-1)topk=LinearSelect(A,a,k);             //对应算法第六步，我定义的数组是从下标0开始的忙，所以这里是k-1
48         else if(a+b<k-1)topk=LinearSelect(C,c,k-a-b);  //对应算法第七步
49         else topk=M;                                   //对应算法第八步
50         
51         }
52         return topk;                                  //返回最终的Top k
53     }
54     public static void main(String[] args) {
55         
56      int s[]={16,9,92,40,25,27};
57      int n=6;
58      int k=2;
59      System.out.print("数组为：");
60      for(int i=0;i<n;i++)
61      {
62          System.out.print(s[i]+",");
63      }
64      System.out.println();
65      System.out.println("第"+k+"小的数为："+LinearSelect(s,n,k));
66      
67     }
68 
69 }

View Code

输出结果为：

数组为：16,9,92,40,25,27,
第2小的数为：16