首页 > 代码库 > 寻找数组N中最大(最小的)M个数(亲自调试可运行)
寻找数组N中最大(最小的)M个数(亲自调试可运行)
当N很小十可以使用方法2,
当N很大时可以使用方法1,从硬盘逐次读入解决;
*寻找长为N的数组的前M大的元素并输出。
*用堆的性质,使用数组N建立一个M大的最大堆,然后输出堆内容即可
*时间复杂度分析: 建堆时间O(M)
*遍历数字,并在堆中比较时间O((N-M)logM)
*总时间复杂度O(M)+ O((N-M)logM)
*
*空间复杂度 O(M)
*/
/*方法2
*使用类快速排序方法解决,“适合较少数据”
*
*时间复杂度O(N)
*
*/
#include<stdio.h> #include<stdlib.h> #include<string.h> #define NDEBUG #include <assert.h> int input(void); void print(int * p,int len); void adjust(int *heap,int heap_size,int index); void swap(int *a,int *b); void built_heap(int *heap,int heap_size,int *a); void find_max(int *heap,int heap_size,int *a,int len); //方法2 void quick_find(int *arry,int len, int M); int partation(int *arry,int len,int start,int end); int main(void) { int heap_size; int *heap; //int a[]={23,54,47,12,6,23,14,1,25,3,5,4,9}; int a[]={1,231,45,69,78,15,36,49,14,36,24,15,89,12,11,69,122,192,126,2125,1,12,4548,125,4755,232, 5,26,24,25,22,22,66,214,1235,2,332,56,66,662,552,225,226,226,2262,262,626,2626,2626,789, 622,15,25,262,551,789,781,895,895,9511,942,412,233,203,202,30,95,2,31,22,12,23,325,235,266,45678,15629,7894}; heap_size=input(); heap=(int *)malloc(sizeof(int)*heap_size); find_max(heap,heap_size,a,sizeof(a)/sizeof(int)); print(heap,heap_size); free(heap); quick_find(a,sizeof(a)/sizeof(int), heap_size); return 0; } void print(int * p,int len) { int i; for(i=0;i<len;i++) printf("%d ",p[i]); printf("\n"); return; } int input(void) { int m; printf("input the M:"); scanf("%d",&m); return m; } //建立堆 void built_heap(int *heap,int heap_size,int *a) { int i; assert(heap!=NULL&&a!=NULL); for(i=0;i<heap_size;i++) heap[i]=a[i]; for(i=(heap_size>>1);i>=0;i--) adjust(heap,heap_size,i); return; } //堆调整 void adjust(int *heap,int heap_size,int index) { int left=(index<<1)+1; int right=(index<<1)+2; int parent=index; assert(heap!=NULL); if(left<heap_size&&heap[left]<heap[parent]) parent=left; if(right<heap_size&&heap[right]<heap[parent]) parent=right; if(parent!=index) { swap(&heap[parent],&heap[index]); adjust(heap,heap_size,parent); } return; } void swap(int *a,int *b) { *a=*a^*b; *b=*a^*b; *a=*a^*b; } void find_max(int *heap,int heap_size,int *a,int len) { int i; int j; assert(heap!=NULL&a!=NULL); if(heap_size>=len) return; built_heap(heap,heap_size,a); for(i=heap_size;i<len;i++) { if(a[i]>heap[0]) { heap[0]=a[i]; adjust(heap,heap_size,0); } } return; } //方法2 void quick_find(int *arry,int len, int M) { int start=0; int end=len-1; int count=M-1; int i; int proe; if(arry==NULL||len<M) return; proe=partation(arry,len-1,start,end); while(proe!=count) { if(proe>count) proe=partation(arry,len-1,start,proe-1); else proe=partation(arry,len-1,proe+1,end); } for(i=0;i<M;i++) printf("%d ",arry[i]); printf("\n"); } int partation(int *arry,int len,int start,int end) { int key=arry[start]; while(start<end) { while(start<end&&arry[end]<=key) end--; if(start<end) arry[start++]=arry[end]; while(start<end&&arry[start]>key) start++; if(start<end) arry[end--]=arry[start]; } arry[start]=key; return start; }
程序运行结果:
“输出两行分别为方法1和方法2结果”
[trageday@lei-yum code_test]$ gcc -o arryN_maxM arryN_maxM.c [trageday@lei-yum code_test]$ ./arryN_maxM input the M:10 2125 2262 2626 4755 2626 45678 9511 7894 15629 4548 45678 15629 9511 7894 4548 2626 2626 4755 2262 2125
寻找数组N中最大(最小的)M个数(亲自调试可运行)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。