线性时间选择（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)即可。

具体算法可描述如下：

privatestaticComparablerandomizedSelect(intp,intr,intk) {
if (p==r) returna[p];
inti=randomizedpartition(p,r),
j=i-p+1;
if (k<=j) {
returnrandomizedSelect(p,i,k);
    } else {
returnrandomizedSelect(i+1,r,k-j);
    }
}

3、代码实现

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

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

例子

解题步骤

(1)把前面25个元素分为5(=⌊29/5⌋)组:

(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(⌊18/5⌋)组：{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个小元素。

privatestaticComparableselect (intp, intr, intk) {
if (r-p<5) {  // 如果元素个数小于5，可以直接返回结果// 用某个简单排序算法对数组a[p:r]排序;bubbleSort(p, r);
returna[p+k-1];
      }
// 将a[p + 5 * i]至a[p + 5 * i + 4]的第3小元素// 与a[p+i]交换位置;// 找中位数的中位数，r-p-4即上面所说的n-5for (inti=0; i<= (r-p-4) /5; i++) {
ints=p+5*i, t=s+4;
for (intj=0; j<3; j++) {
bubble(s, t-j);
         }
MyMath.swap(a, p+i, s+2);
      }
Comparablex=select(p, p+ (r-p-4) /5, (r-p+6)/10);
inti=partition(p,r,x), j=i-p+1;
if (k<=j) {
returnselect(p,i,k);
      } else {
returnselect(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、参考资料

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