程序员面试宝典-20个有序数组求最大500个元素

xiaoxiao2021-02-28  21

程序员面试宝典-20个有序数组求最大500个元素


20个有序数组求最大500个元素

题目

题目:有20个数组, 每个数组里面有500个数, 升序排列, 求出这10000个数字中最大的500个。 求复杂度。

最直接的思路

暴力法,直接将20个数组中的数据全部合并,重新排序,然后取出最大的500个。 如果空间允许的情况下,排序的时间复杂度根据选择的排序算法来决定。

大顶堆的解法

从20个数组中各取一个数,并记录每个数的来源数组,建立一个含20个元素的大根堆。 此时堆顶就是最大的数,取出堆顶元素,并从堆顶元素的来源数组中取下一个数加入堆,再取最大值,一直这样进行500次即可。 时间复杂度:500*log(20) 怎么记录每个数的来源数组? 用结构体记录,一个成员记录值,一个记录来源,按成员值比较 也可以单独用一个数组存储。

/* 原题:有20个数组,每个数组里面有500个数,升序排列,求出这10000个数中最大的500个,求复杂度。 算法实现:为简化,设有5个数组,每个数组里面有10个数,升序排列,求出50个数中最大的5个数。 */ #include<iostream> using namespace std; void CreatHeap(int s[],int n) //建堆,最大堆即首元素是最大的 { //从最后一个非叶子节点开始 int i,j,k; i=n/2-1; j=2*i+1; for(k=i;k>=0;k--) { i=k; j=2*i+1; while(j<=n) { if(j+1<=n&&s[j]<s[j+1])j=j+1; if(s[i]<s[j]) { int temp=s[i]; s[i]=s[j]; s[j]=temp; i=j; j=2*i+1; } else break; } } } int main() { int a[5][10]={ {1,2,3,4,5,6,7,8,45,47}, {11,12,13,14,15,16,17,18,19,20}, {21,22,23,24,25,26,27,28,29,30}, {31,32,33,34,35,36,37,38,39,40}, {41,42,43,44,45,46,47,48,49,50}}; int b[5]={9,9,9,9,9};//作为标记当前取该数组的哪个 int temp[5]; int count=0; int result[10]; for(int m=0;m<10;m++) { for(int i=0;i<5;i++) { int r=b[i]; temp[i]=a[i][r]; } CreatHeap(temp,5);//需要标记最大的值temp[0]在那个数组中 int max=temp[0]; result[count++]=max; for(int i=0;i<5;i++) { int k=b[i]; if(max==a[i][k]) { b[i]=b[i]-1; break; } } } for(int i=0;i<10;i++) { cout<<result[i]<<endl; } }
转载请注明原文地址: https://www.6miu.com/read-2250027.html

最新回复(0)