这个题也是个比较有名的面试题.当然有很多变种.
题目意思基本是:从一个数据量很大的数组里找前N大的元素.不允许排序.
这个题有两个比较好的思路:
思路一:用快速排序的思想,是思想,不是要排序;
思路二:用最大堆的思想.
我暂时只实现了思路一,思路二我之后实现了会补上.
思路一比较简单了.我们先用快排的思想找出第n大的数,然后带上后面n-1个就完事了.因为后面的都比支点数大.
怎么找第n大的数?我在之前的博客写过,请移步到 找第n大的数
代码:
#include<stdio.h>
#include<stdlib.h> /*找出第n大的数的下标*/
int choose_nth(int a[], int startIndex, int endIndex, int n); /*找出前n大的数*/
void choose_max_n(int a[],int startIndex, int endIndex, int n); int main(int argc, char *argv)
{
int a[] = {,,,,,,,,,,};
int n,i;
printf("数组是:\n");
int an = sizeof(a)/sizeof(int);
for(i = ; i < an; ++i)
printf("%d ",a[i]);
printf("\n"); printf("你想找最大的前面几个数:");
scanf("%d",&n); choose_max_n(a, , an - , n); return ;
} void choose_max_n(int a[], int startIndex, int endIndex, int n)
{
int i = choose_nth(a, startIndex, endIndex, n); printf("最大的前N个数是:\n");
for(; i <= endIndex; ++i)
printf("%d ",a[i]);
printf("\n");
} int choose_nth(int a[], int startIndex, int endIndex, int n)
{
int midOne = a[startIndex];
int i = startIndex, j = endIndex;
if(i == j)
return i; if(i < j)
{
while(i < j)
{
for(; i < j; j--)
if(a[j] < midOne)
{
a[i++] = a[j];
break;
} for(; i < j; i++)
if(a[i] > midOne)
{
a[j--] = a[i];
break;
} } a[i] = midOne;
int th = endIndex - i + ; if(th == n)
{
return i;
}
else
{
if(th > n)
{
return choose_nth(a, i + , endIndex, n);
}
else
{
return choose_nth(a, startIndex, i - , n - th);
}
} }
}
结果:
数组是: 你想找最大的前面几个数:
最大的前N个数是:
之后会补上用最大堆思想来做的代码.