TOP,K算法

程序员面试题狂想曲：第三章续、Top K算法问题的实现收藏程序员面试题狂想曲：第三章续、Top K算法问题的实现作者：July，zhouzhenren，yansha。

致谢：微软100题实现组，狂想曲创作组。

时间：2011年05月08日微博：/julyweibo 。

出处：/v_JULY_v 。

wiki：/。

-----------------------------------------------前奏在上一篇文章，程序员面试题狂想曲：第三章、寻找最小的k个数中，后来为了论证类似快速排序中partition的方法在最坏情况下，能在O（N）的时间复杂度内找到最小的k个数，而前前后后updated了10余次。

所谓功夫不负苦心人，终于得到了一个想要的结果。

简单总结如下（详情，请参考原文第三章）：1、RANDOMIZED-SELECT，以序列中随机选取一个元素作为主元，可达到线性期望时间O（N）的复杂度。

2、SELECT，快速选择算法，以序列中“五分化中项的中项”，或“中位数的中位数”作为主元（枢纽元），则不容置疑的可保证在最坏情况下亦为O（N）的复杂度。

本章，咱们来阐述寻找最小的k个数的反面，即寻找最大的k个数，但此刻可能就有读者质疑了，寻找最大的k个数和寻找最小的k个数，原理不是一样的么?是的，的确是一样，但这个寻找最大的k个数的问题的实用范围更广，因为它牵扯到了一个Top K算法问题，以及有关搜索引擎，海量数据处理等广泛的问题，所以本文特意对这个Top K算法问题，进行阐述以及实现（侧重实现，因为那样看起来，会更令人激动人心），算是第三章的续。

ok，有任何问题，欢迎随时不吝指正。

谢谢。

说明关于寻找最小K个数能做到最坏情况下为O（N）的算法及证明，请参考原第三章，寻找最小的k个数，本文的代码不保证O（N）的平均时间复杂度，只是根据第三章有办法可以做到而已（如上面总结的，2、SELECT，快速选择算法，以序列中“五分化中项的中项”，或“中位数的中位数”作为主元或枢纽元的方法，原第三章已经严格论证并得到结果）。

第一节、寻找最小的第k个数在进入寻找最大的k个数的主题之前，先补充下关于寻找最k小的数的三种简单实现。

由于堆的完整实现，第三章：第五节，堆结构实现，处理海量数据中已经给出，下面主要给出类似快速排序中partition过程的代码实现：寻找最小的k个数，实现一：view plaincopy to clipboardprint?//copyright@ mark allen weiss && July && yansha//July，yansha、updated，2011.05.08.//本程序，后经飞羽找出错误，已经修正。

//随机选取枢纽元，寻找最小的第k个数#include <iostream>#include <stdlib.h>using namespace std;int my_rand(int low, int high){int size = high - low + 1;return low + rand() % size;}//q_select places the kth smallest element in a[k]int q_select(int a[], int k, int left, int right){if(k>right){cout<<"---------"<<endl; //为了处理当k大于数组中元素个数的异常情况return false;}//真正的三数中值作为枢纽元方法，关键代码就是下述六行int midIndex = (left + right) / 2; if(a[left] < a[midIndex])swap(a[left], a[midIndex]);if(a[right] < a[midIndex])swap(a[right], a[midIndex]);if(a[right] < a[left])swap(a[right], a[left]);swap(a[midIndex], a[right]);int pivot = a[right]; //之前是int pivot = right，特此，修正。

// 申请两个移动指针并初始化int i = left;int j = right-1;// 根据枢纽元素的值对数组进行一次划分for (;;){while(a[i] < pivot)i++;while(a[j] > pivot)j--;if (i < j)swap(a[i], a[j]);elsebreak;}swap(a[i], a[right]);/* 对三种情况进行处理：(m = i - left + 1)1、如果m=k，即返回的主元即为我们要找的第k小的元素，那么直接返回主元a[i]即可;2、如果m>k，那么接下来要到低区间A[0....m-1]中寻找，丢掉高区间;3、如果m<k，那么接下来要到高区间A[m+1...n-1]中寻找，丢掉低区间。

*/ int m = i - left + 1;if (m == k){cout<<a[i]<<endl;for(i-=1;i>=0;i--)cout<<a[i]<<endl;}else if(m > k)return q_select(a, k, left, i - 1);elsereturn q_select(a, k - m, i + 1, right);}int main(){int i;int a[] = {7, 8, 9, 54, 6, 4, 11, 1, 2, 33};q_select(a, 4, 0, sizeof(a) / sizeof(int) - 1);return 0;}寻找最小的第k个数，实现二：view plaincopy to clipboardprint?//copyright@ July//yansha、updated，2011.05.08。

// 数组中寻找第k小元素，实现二#include <iostream>using namespace std;const int numOfArray = 10;// 这里并非真正随机int my_rand(int low, int high){int size = high - low + 1;return low + rand() % size;}// 以最末元素作为主元对数组进行一次划分int partition(int array[], int left, int right){int pos = right;for(int index = right - 1; index >= left; index--){if(array[index] > array[right])swap(array[--pos], array[index]);}swap(array[pos], array[right]);return pos;}// 随机快排的partition过程int random_partition(int array[], int left, int right){// 随机从范围left到right中取一个值作为主元int index = my_rand(left, right);swap(array[right], array[index]);// 对数组进行划分，并返回主元在数组中的位置return partition(array, left, right);}// 以线性时间返回数组array[left...right]中第k小的元素int random_select(int array[], int left, int right, int k){// 处理异常情况if (k < 1 || k > (right - left + 1))return -1;// 主元在数组中的位置int pos = random_partition(array, left, right);/* 对三种情况进行处理：(m = i - left + 1)1、如果m=k，即返回的主元即为我们要找的第k小的元素，那么直接返回主元array[i]即可;2、如果m>k，那么接下来要到低区间array[left....pos-1]中寻找，丢掉高区间;3、如果m<k，那么接下来要到高区间array[pos+1...right]中寻找，丢掉低区间。

*/ int m = pos - left + 1;if(m == k)return array[pos];else if (m > k)return random_select(array, left, pos - 1, k);elsereturn random_select(array, pos + 1, right, k - m);}int main(){int array[numOfArray] = {7, 8, 9, 54, 6, 4, 2, 1, 12, 33};cout << random_select(array, 0, numOfArray - 1, 4) << endl;return 0;}寻找最小的第k个数，实现三：view plaincopy to clipboardprint?//求取无序数组中第K个数，本程序枢纽元的选取有问题，不作推荐。

//copyright@ 飞羽//July、yansha，updated，2011.05.05。

#include <iostream> #include <time.h> using namespace std;int kth_elem(int a[], int low, int high, int k){int pivot = a[low]; //下面的阐述是这样一个事实：基于数组元素是固定的，而非随机生成的。

//这个程序之所以做不到O（N）的最最重要的原因，就在于这个枢纽元的选取。

//我们知道，这个枢纽元是否选择得当，直接决定了最后的时间复杂度是否能做到O（N）。

//在第一节末，是三数中值作为枢纽元，第二节，此枢纽元是随机选取，//在稍后的updated 中，是五分化中项的中项作为枢纽元中，//每一个枢纽元的选取都是完全不同于此前快速排序的以第一个，或最后一个元素作为枢纽元的方案。