编程之美 2.5 寻找最大的K个数

问题： 有很多个无序的数，假定他们各不相等，怎么选出其中最大的若干个数呢?

 

解答：寻找N个数中最大的K个数，本质上就是寻找最大的K个数中最小的那个，也就是寻找第K大的数，可以使用二分搜索的策略。假设N个数中最大的数为Vmax,最小的数为Vmin，那么这N个数中的第K大的数一定在[Vmin,Vmax]之间，可以在这个区间中二分搜索N个数中第K大的数p。

 

#include <stdio.h>
#include <limits.h>

int f(int* a, int length, int mid) {
	//返回a[0...length]中大于等于mid的数的个数
	int num = 0;
	for(int i=0; i<length; i++) {
		if(a[i] >= mid)
			num++;
	}
	return num;
}

int findK(int* a, int length,int max, int min,int k) {
	//返回第K的的数
	int mid;
	while(max > min+1) {
		mid = (max + min)/2;
		if(f(a,length,mid) >= k)
			//若a[0...length]中大于等于mid的数超过k个
			//则说明第k大的数在[mid,max]中
			min = mid;
		else max = mid;
	}
	return min;
}

int main(int argc, char * argv[] ) {
	int array[10]={5,3,9,10,2,6,4,7,1,8};
	int vMin = INT_MAX,vMax = INT_MIN;
	int k=4;

	for(int i=0; i<10; i++) {
		if(array[i] < vMin)
			vMin = array[i];
		if(array[i] > vMax)
			vMax = array[i];
	}


	int themaxK = findK(array,10,vMax,vMin,k);
	printf("The max k number is %d\n",themaxK);

	return 0;
}

 

评论

3 楼 chriszeng87 2011-05-18  

findK函数中while循环的结束条件应该是有问题的

2 楼 chriszeng87 2011-05-17  

AsWater 写道

    如果这是一道面试题，我是主考官，我只能给楼主0分。
    第一，这段代码是基于一个假设“给出的N个数都是整数”，这个假设可能是错误的。
    第二，就是前面一点的假设是正确的，我们要的结果是“选出其中最大的K个数”，而不是“求第K大的数”，要的结果是多个数，不是一个数。就以代码中的例子来说，对于数组{5,3,9,10,2,6,4,7,1,8}，给出K=4的时候，我们需要的结果是最大的4个数10，9，8，7，而不是说“第四大的数是7”。

第二点我想解释一下，如果知道“第四大的数是7”，可以遍历一遍数组即可得到所有4个最大的数，找到第四大的数是前面的铺垫，我偷了个懒没写的

1 楼 AsWater 2011-05-17  

    如果这是一道面试题，我是主考官，我只能给楼主0分。
    第一，这段代码是基于一个假设“给出的N个数都是整数”，这个假设可能是错误的。
    第二，就是前面一点的假设是正确的，我们要的结果是“选出其中最大的K个数”，而不是“求第K大的数”，要的结果是多个数，不是一个数。就以代码中的例子来说，对于数组{5,3,9,10,2,6,4,7,1,8}，给出K=4的时候，我们需要的结果是最大的4个数10，9，8，7，而不是说“第四大的数是7”。