线性时间选择（Top K）问题（Java）

1、前置介绍

定义

选择问题（select problem）是指在n个元素的集合中，选出某个元素值大小在集合中处于第k位的元素，
即所谓的求第k小元素问题(kth-smallest)。

元素选择问题的一般提法

给定具有n个元素的一个线性序集和一个整数k，其中，l<=k<=n，题目要求找出这n个元素中第k小的元素， 即如果将这n 个元素依其线性序排列时，排在第k个的元素即为要找的元素。

易知，

• 当k=l时，就是要找最小元素；
• 当k=n时，就是要找最大元素；
• 当k= (n+l)/2时，称为找中位数。

在某些特殊情况下，很容易设计出解选择问题的线性时间算法。

例如，找n个元素的最小元素和最大元素显然可以在O(n)时间完成。如果k<=n/logn, 通过堆排序算法可以在
O(n+klogn) = O(n)时间内找出第k小元素。 当k>=n-n/logn时也一样。

2、分治法求解

一般的选择问题， 特别是中位数的选择问题似乎比找最小元素要难。但事实上， 从渐近阶的意义上看，它们是一样的。
一般的选择问题也可以在OCn) 时间内得到解决。

设原表长度为n，假定经过一趟划分，分成左右两个子表，其中左子表是主元及其左边元素的子表，设其长度为j，右子表是主元右边元素的子表。那么，若k=j，则主元就是第k小元素；否则若k<j，第k小元素必定在左子表中，需求解的子问题成为在左子表中求第k小元素；若k>j，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-j小元素。

下面要讨论解一般的选择问题的分治算法randomizedSelect。该算法实际上是模仿快速排序算法设计出来的。
其基本思想也是对输入数组进行递归划分。与快速排序算法不同的是，它只对划分出的子数组之一进行递归处理。

随机选主元算法

假定表中元素各不相同，并且随机选择主元，即在下标区间[left,right]中随机选择一个下标r，以该下标处的元素为主元。

要找数组arr[0:n-1]中第K小元素只要调用randomizedSelect(arr, 0, n -1, k)即可。

具体算法可描述如下：

private static Comparable randomizedSelect(int p,int r,int k) {
    if (p==r) return a[p];
    int i=randomizedpartition(p,r),
    j = i - p + 1;
    if (k<=j) {
        return randomizedSelect(p,i,k);
    } else {
        return randomizedSelect(i+1,r,k-j);
    }
}

3、代码实现

• 将n个输入元素划分成 $\lceil n/5 \rceil$个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共 $\lceil n/5 \rceil$个。

• 递归调用select来找出这 $\lceil n/5 \rceil$个元素的中位数。如果 $\lceil n/5 \rceil$是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。

例子

解题步骤

(1)把前面25个元素分为5(= $\lfloor 29/5 \rfloor$)组:
(8,31,60,33,17)，(4,51,57,49,35)，(11,43,37,3,13)，(52,6,19,25,32)，(54,16,5,41,7)

(2)提取每一组的中值元素，构成集合{31,49,13,25,16}；

(3)递归地使用算法求取该集合的中值，得到m=25:

(4)根据m=25,把29个元素划分为3个子数组：

• P = {8,17,4,11,3,13,6,19,16,5,7,23,22}
• Q = {25}
• R = {31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}

(5)由于P=13、Q=1、k=18，所以放弃P、Q，使k=18-13-1=4,对R递归地执行本算法：

(6)将R划分成3( $\lfloor 18/5 \rfloor$)组：
{31,60,33，51,57}，{49,35，43,37,52}，{32,54,41,46,29}

(7)求取这3组元素的中值元素分别为：{51,43,41}，这个集合的中值元素是43；

(8)根据43将R划分成3组：
{31,33,35,37,32,41,29},{43},{60,51,57,49,52,54,46}

(9)因为k=4,第一个子数组的元素个数大于k,
所以放弃后面两个子数组，以k=4对第一个子
数组递归调用本算法；

(10)将这个子数组分成5个元素的一组：
{31,33,35,37,32},取其中值元素为33：

(11)根据33，把第一个子数组划分成{31,32,29},{33},{35,37,41}

(12)因为k=4,而第一、第二个子数组的元素个数为4，所以33即为所求取的第18个小元素。

private static Comparable select (int p, int r, int k) {
      if (r - p < 5) {  // 如果元素个数小于5，可以直接返回结果
        // 用某个简单排序算法对数组a[p:r]排序;
        bubbleSort(p, r);
        return a[p + k - 1];
      }
      // 将a[p + 5 * i]至a[p + 5 * i + 4]的第3小元素
      // 与a[p+i]交换位置;
      // 找中位数的中位数，r-p-4即上面所说的n-5
      for (int i = 0; i<= (r - p - 4) / 5; i++) {
         int s = p + 5 * i, t = s + 4;
         for (int j = 0; j < 3; j++) {
           bubble(s, t - j);
         }
         MyMath.swap(a, p+i, s+2);
      }
      Comparable x = select(p, p + (r - p - 4) / 5, (r - p + 6)/ 10);
      int i = partition(p,r,x), j = i - p + 1;
      if (k <= j) {
        return select(p,i,k);
      } else {
        return select(i+1,r,k-j);
      }
}

4、复杂度分析

在最坏情况下，算法randomizedSelect需要O(n²)计算时间（在找最小元素时，总是在最大元素处划分）

但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。

如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。

例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n) 。

由此可得T(n)=O(n)。

设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。(备注：就是说明递归子问题规模是下降的，划分后的两个子数组分别至多有3n/4个元素)

上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20
=εn，0<ε<1。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。

递归树

5、扩展

分组为什么5个元素一组？3个一组或7个一组行不行？

分析：递归调用

1、求x的工作量与中位数集合的规模有关,其值=n/t有关，t为每组元素数，t越大，其规模越小

2、规约后子问题大小与分组元素数t有关，t越大，子问题规模大。

6、参考资料

• 算法分析与设计（第四版）