关于查找数组中最小的k个元素的全面讨论与解答

关于查找数组中最小的k个元素的全面讨论与解答

作者：July、Sorehead、wocaoqwer 、飞羽等人
参考：
I、本人整理的微软面试第5题
II、本人发的帖子：
[推荐] 横空出世，席卷Csdn：记微软等100题系列数次被荐[100题维护地址]
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html
---------------------------------------

引言：

以下是我和网友Sorehead关于查找最小的k个元素的讨论，全部的讨论都在我的这个帖子上（第6页）：
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9_6.html
我看到，关于这个查找最小的k个元素的问题，
该采用何种方法，其时间复杂度到底可以优化到多少，网上有很多种说法，但都很不明确，清晰明了。

现在，整理成文，希望，给自己和读者一个清晰的思路、明确的解答。
有不正之处，还望不吝指正。

题目描述：

5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

此题，是我之前整理的微软100题中的第5题，最初在我上传的答案V0.2版[第1-20题答案]中，

我最初提供的答案如下：

//July 2010/10/18
//引用自116 楼 wocaoqwer 的回复。
#include<iostream>
using namespace std;

class MinK{
public:
MinK(int *arr,int si):array(arr),size(si){}

bool kmin(int k,int*& ret){
if(k>size)
{
ret=NULL;
return false;
}
else
{
ret=new int[k--];
int i;
for(i=0;i<=k;++i)
ret[i]=array[i];
for(int j=(k-1)/2;j>=0;--j)
shiftDown(ret,j,k);
for(;i<size;++i)
if(array[i]<ret[0])
{
ret[0]=array[i];
shiftDown(ret,0,k);
}
return true;
}
}

void remove(int*& ret){
delete[] ret;
ret=NULL;
}

private:
void shiftDown(int *ret,int pos,int length){
int t=ret[pos];
for(int s=2*pos+1;s<=length;s=2*s+1){
if(s<length&&ret[s]<ret[s+1])
++s;
if(t<ret[s])
{
ret[pos]=ret[s];
pos=s;
}
else break;
}
ret[pos]=t;
}

int *array;
int size;
};

int main()
{
int array[]={1,2,3,4,5,6,7,8};
MinK mink(array,sizeof(array)/sizeof(array[0]));
int *ret;
int k=4;
if(mink.kmin(k,ret))
{
for(int i=0;i<k;++i)
cout<<ret[i]<<endl;
mink.remove(ret);
}
return 0;
}

Sorehead
然后，网友Sorehead在我的这个帖子上，看了我上传的答案之后，回复到：

#533楼 得分：0回复于：2011-02-24 22:26:02
第五题：
楼主的答案使用堆排序倒是很不错的方法。
我比较偷懒，采用链表来保存k个元素，链表中节点元素按照大小排序。
当然这种方法效率不是很高，如果k比较大，可以采用平衡二叉树或红黑树的方法来处理。

July
我回复他：

#534楼 得分：0回复于：2011-02-25 09:03:09
也可以：
用类似快排的partition的方法，只求2边中的一边，在O(N)时间得到第k大的元素v；
再扫描一遍( O(N) )，得到所有小于等于v的元素。

其中，快速排序每一趟比较用时O（n），要进行lgn次比较，才最终完成整个排序。
所以快排的复杂度才为O（n*lgn）。

像现在，只需要，找到第k大的元素，排一趟是O（n），
排俩趟是O（2n），其中第二趟，可以在第一趟后选择排序哪边 //其实是递归。
即只要排一边了，找到第k大的元素，是O（N）的复杂度，
最后遍历那一边O（k），输出这k个元素，即可。

所以，总的运行时间复杂度为O（N）。//下文，Sorehead认为此平均复杂度为O（n*logk），非O（N）。
（如果，要有序输出的话，则再将那k的元素排序，时间复杂度为O（N+klgk）。） //Sorehead不这么认为，参考下文。

Sorehead
而后，网友Sorehead给出了答复：

#548楼 得分：0回复于：2011-03-02 11:34:31
楼主说到使用快速排序，这个方法也不错，时间复杂度平均为O(nlogn)，最坏情况下是O(n*n)，而堆排序恒定O(nlogn)。
但楼主所说在O(N)时间得到第k大的元素，我没想到有什么办法，如果能够做到这点，压根就不需要任何复杂的方法，简单的再次遍历一次就可以得到所有需要的值了，甚至都不需要再次遍历，而在获取到这个元素的过程中就已经可以达到目的了。

使用平衡二叉树或者红黑树，先取前k个元素创建树，耗费时间是log1+log2+...+log(k-1)，简便起见为klogk，剩下的n-k个元素的时间复杂度为(n-k)logk，总体复杂度为O(nlogk)。

如果使用快速排序，是可以优化的，毕竟我们的目的不是将全部数据进行排序。假设用于分隔记录的枢轴元素为v，一趟排序后如果v<k，那前半部分记录就无需再做处理，如果v>k，那后半部分也无需再做处理，如果v=k，任务完成。但最坏情况下时间复杂度依然是O(n*n)。
如果使用堆排序，我觉得时间复杂度和平衡二叉树、红黑树也是一样的，为O(nlogk)。

还有一个情况必须说明一下，当k>=n，按照上面的说明，时间复杂度就变更为O(nlogn)，而实际上这时候并不需要做什么处理，直接返回所有n个元素即可。
这点明显可以看出有地方我们处理不正确，就是当k>n/2 && k<n时，应该换个思路，变成去查找最大的(n-k)个元素了，这样才是合理的。

July
我为了证明：第五题，“用快速排序中类似的分治法，是可以做到O（N）的”，我说：

#555楼 得分：0回复于：2011-03-02 21:28:38
类似快排中的分割算法：
每次分割后都能返回枢纽点在数组中的位置s,然后比较s与k的大小
若大的话，则再次递归划分array[s..n]，
小的话，就递归array[left...s-1] //s为中间枢纽点元素。
否则返回array[s]，就是partition中返回的值。 //就是要找到这个s。

找到符合要求的s值后，再遍历输出比s小的那一边的元素。

即：如果第一次 分划，找到的第s小符合要求目标m，则停止，
如果找到的第s小，s<m，则到 s的右边继续找
如果找到的第s小，s>m，则 到s的左边继续找。

并引用了飞羽的程序，做补充说明：

#557楼 得分：0回复于：2011-03-02 21:32:04
//求取无序数组中第K个数
#include <iostream>
#include <cstdio>
#include <cstdlib>
//#include "QuickSort.cpp"
using namespace std;

int kth_elem(int a[],int low, int high,int k)
{
int pivot=a[low];
int low_temp = low;
int high_temp = high;
while(low<high)
{
while(low<high&&a[high]>pivot)
--high;
a[low]=a[high];
while(low<high&&a[low]<pivot)
++low;
a[high]=a[low];
}
a[low]=pivot;
//上面为快排的那个分割算法
//以下就是主要思想中所述的内容
if(low==k-1)
return a[low];
else if(low>k-1)
return kth_elem(a,low_temp,low-1,k);
else
return kth_elem(a,low+1,high_temp,k);
}

int main()
{
int a[20];
int k;
for(int i=0;i<20;i++)
{
a[i] = rand()%100; //随机地生成序列中的数
printf("%3d ",a[i]);
if(i%5==4)
cout << endl;
}
cin >> k;
cout << "the" << k << "th number is:" << kth_elem(a,0,19,k)<<endl;
//下面用快排对a进行排序，验证上面的求解结果；
cout << endl;
getchar();
return 0;
}

Sorehead
之后，Sorehead再次回复我：

#561楼 得分：0回复于：2011-03-03 11:20:15
关于第五题回复楼主：
你提供的代码中明显可以看出时间复杂度不是O(n)，kth_elem被调用的次数并不是常数，而是由n和k决定的，一般情况下时间复杂度是O(logk)，最快情况下应该是O(logn)。

此外，函数kth_elem中while(low<high)循环里面还有low<high这样的判断有点多余。 //他说的是对的，后来，我改正了。

July
但，我依旧没有死心，我仍然认为，可以做到O（N），于是我从算法导论一书上，找到了：

#564楼 得分：0回复于：2011-03-03 16:38:03
关于时间复杂度为O（N）的证明，我找到了。
在算法导论上，第九章中，以期望线性时间做选择，一节中，
我找到了这个 寻找数组中第k小的元素的，平均时间复杂度为O（N）的证明。

中文版是 第110页，英文版约是第164页。

不是一趟O（N），而是最终找到那第k个数，然后将其输出，的复杂度为O（N）。
（或者，O（n+k），最后遍历那k个元素输出。）。

Sorehead
然，最终，Sorehead终于一针见血的指出我的问题与考虑不周之处：

#570楼 得分：0回复于：2011-03-09 16:28:51
回复楼主：
　　我之前给出的“一般情况下时间复杂度是O(logk)，最坏（当时写成最快了）情况下应该是O(logn)”只是我大致的一个推测，而且这个指的仅仅是kth_elem的运行次数，并不是真正的时间复杂度。
　　我依然不认为kth_elem是O(n)的时间复杂度，平均时间复杂度我推测不出来，感觉是O(nlogk)，但最坏情况下应该是O(n*k)。一个简单例子就是这么一个递增序列：1,2,3,4,5。
　　按照函数实现，k=1需要遍历1次。。。k=5就需要遍历5次。

　　《算法导论》中“以线性期望时间做选择”我看过了，楼主的代码虽然很像，但一个细节的缺失导致了很大的问题，就是关键数据的选取，书上每次都是随机取其中一个数据，而不是你的程序中只取第一个数据。每次随机取能够很大程度避免最坏情况发生。
　　类似的快速排序就是个很不稳定的算法，关键数据的选取是个很大的问题，如果选择不当，就会变成大家最熟悉的冒泡法。

Sorehead
并特别给出了他的十分清晰的思路：

#571楼 得分：0回复于：2011-03-09 16:29:58
关于第五题：
这两天我总结了一下，有以下方法可以实现：
1、第一次遍历取出最小的元素，第二次遍历取出第二小的元素，依次直到第k次遍历取出第k小的元素。这种方法最简单，时间复杂度是O(k*n)。看上去效率很差，但当k很小的时候可能是最快的。
2、对这n个元素进行排序，然后取出前k个数据即可，可以采用比较普遍的堆排序或者快速排序，时间复杂度是O(n*logn)。这种方法有着很大的弊端，题目并没有要求这最小的k个数是排好序的，更没有要求对其它数据进行排序，对这些数据进行排序某种程度上来讲完全是一种浪费。而且当k=1时，时间复杂度依然是O(n*logn)。
3、可以把快速排序改进一下，应该和楼主的kth_elem一样，这样的好处是不用对所有数据都进行排序。平均时间复杂度应该是O(n*logk)。
4、使用我开始讲到的平衡二叉树或红黑树，树只用来保存k个数据即可，这样遍历所有数据只需要一次。时间复杂度为O(n*logk)。后来我发现这个思路其实可以再改进，使用堆排序中的堆，堆中元素数量为k，这样堆中最大元素就是头节点，遍历所有数据时比较次数更少，当然时间复杂度并没有变化。
5、使用计数排序的方法，创建一个数组，以元素值为该数组下标，数组的值为该元素在数组中出现的次数。这样遍历一次就可以得到这个数组，然后查询这个数组就可以得到答案了。时间复杂度为O(n)。如果元素值没有重复的，还可以使用位图方式。这种方式有一定局限性，元素必须是正整数，并且取值范围不能太大，否则就造成极大的空间浪费，同时时间复杂度也未必就是O(n)了。当然可以再次改进，使用一种比较合适的哈希算法来代替元素值直接作为数组下标。

Sorehead
最后，还给出了计数排序的实现代码：

下面是采用计数排序方法实现的代码，通过一次遍历得知最大值和最小值，然后用元素值减去最小值作为计数数组下标，最大值减最小值为计数数组空间大小：
void get_min_nums(int *arr, int n, int *result, int k)
{
int max, min, len, i;
int *count;

if (arr == NULL || n <= 0 || result == NULL || k <= 0)
return;

max = min = arr[0];
for (i = 1; i < n; i++)
{
if (arr[i] > max)
max = arr[i];
else if (arr[i] < min)
min = arr[i]; //以上，通过一次遍历得知最大值和最小值
}

len = max - min + 1;
if ((count = malloc(sizeof(int) * len)) == NULL)
return;
memset(count, 0, sizeof(int) * len);

for (i = 0; i < n; i++)
count[arr[i] - min]++; //元素值减去最小值作为计数数组下标

for (i = 0; i < len; i++)
{
if (count[i] == 0)
continue;

if (count[i] >= k)
{
while (k--)
*result++ = min + i;
break;
}

k -= count[i];
while (count[i]--)
*result++ = min + i;
}

free(count);
}

July
我暂时也还不知道上述的讨论有多少错误，但他一针见血的指出我的考虑不周之处，非常感谢。同时，也让我发现了，此前上传的前60题的答案，有很多值得商榷的地方，我的目的，就是尽我最大努力，把这些不足与漏洞一一找出来。最终，达到最好的优化。

最后，还请各位读者，针对上文，或我上传的前60题的答案，不吝批评指正，或赐教。本人感激不尽。

更多的详情，请参见，此帖子第6页内容：http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9_6.html。
完。