广州双城热恋创意文化传播有限公司

现在的位置: 主页 > 主打产品 > 文章列表

文章正文

经典算法学习——求数组里面第N大的数

作者:广州双城热恋创意文化传播有限公司 来源:www.999loveyou.com 发布时间:2017-09-07 13:36:20
经典算法学习——求数组里面第N大的数

这是一道面试的算法题,当然可以用很多排序算法来实现,这些都是比价常规的。但是这道题要求不能排序,并且时间复杂度不能超过O(n^2).这里我们借用快速排序的衍生算法来实现。关于快速排序的实现,可以参考《经典算法学习——快速排序》这篇博客。示例代码上传至:https://github.com/chenyufeng1991/Front-N。

每一次的快排,都需要找一个基准值,然后从数组的两边交替开始和基准值比较,右边比基准值小的数移到左边,左边比基准值大的数移到右边,移到最后,只剩下一个位置了a[i],然后把基准值填入到a[i]中。此时,在基准值右边的数都比支点大。如果此时基准值的下标为i, 那么这个基准值就是第(endIndex-i+1)大的数了。endIndex是最后一个数的下标。

我们的目标是要找第N大的数,如果endIndex-i+1 = n,表示这个数我们找到了,具体说明如下:

记th = endIndex - i + 1 (表示当前下标为i的数字排名第th位)。find(a,startIndex,endIndex,n)

(1)th = n,返回基准值;

(2)th > n,说明第n大的数在基准值右边,所以在右边继续找:find(a,i+1,endIndex,n);

(3)th < n,说明第n大的数在基准值左边,在左边找第(n-th)大的数即可;find(a,startIndex,i-1,n-th);

具体代码实现如下:

// // main.c // FrontN // // Created by chenyufeng on 16/1/28. // Copyright © 2016年 chenyufengweb. All rights reserved. // #include int choose_nth(int a[],int startIndex, int endIndex, int n); int main(int argc, const char * argv[]) { int a[] = {150,111,1000,99,300,10,189}; int ans = choose_nth(a, 0, 6, 1); printf("第1大的数是:%d\n", ans); return 0; } int choose_nth(int a[], int startIndex, int endIndex, int n) { int midOne = a[startIndex];//把第一个值作为支点 int i = startIndex, j = endIndex; if(i == j) //递归出口之一 return a[i]; if(i < j){ while(i < j){ while (i < j && a[j] >= midOne) { j--; } if (i < j) { a[i++] = a[j]; } while (i < j && a[i] < midOne) { i++; } if (i < j) { a[j--] = a[i]; } } a[i] = midOne;//支点归位 //此时a[i]这个数必定处于它真正的位置上,左边的都比他小,右边的都比他大; int th = endIndex - i + 1;//计算下标为i的数第几大,都使用下标进行计算; if(th == n){//正好找到 return a[i]; } else{ if(th > n)//在支点右边找 return choose_nth(a, i + 1, endIndex, n); else//在支点左边找第(n-th)大,因为右边th个数都比支点大 return choose_nth(a, startIndex, i - 1, n - th); } } return 0; }

通过查看代码知道,其中的主体部分就是快速排序。

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:仙桃网站制作 http://xiantao.666rj.com

COPYRIGHT © 2015 广州双城热恋创意文化传播有限公司 ALL RIGHTS RESERVED. 网站地图 技术支持:肥猫科技
精彩专题:网站建设
购买本站友情链接、项目合作请联系客服QQ:2500-38-100