首页 > 代码库 > 找出数组前N大的数
找出数组前N大的数
这个题也是个比较有名的面试题.当然有很多变种.
题目意思基本是:从一个数据量很大的数组里找前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[] = {1,4,111,32,45,1000,99,300,8,22,189}; int n,i; printf("数组是:\n"); int an = sizeof(a)/sizeof(int); for(i = 0; i < an; ++i) printf("%d ",a[i]); printf("\n"); printf("你想找最大的前面几个数:"); scanf("%d",&n); choose_max_n(a, 0, an - 1, n); return 0;}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 + 1; if(th == n) { return i; } else { if(th > n) { return choose_nth(a, i + 1, endIndex, n); } else { return choose_nth(a, startIndex, i - 1, n - th); } } }}
结果:
数组是:1 4 111 32 45 1000 99 300 8 22 189 你想找最大的前面几个数:5最大的前N个数是:99 111 300 1000 189
之后会补上用最大堆思想来做的代码.
找出数组前N大的数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。