编程之美 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;}? 1 楼 AsWater 2011-05-17 如果这是一道面试题，我是主考官，我只能给楼主0分。