如何用TopN算法在10亿个整数中找出前1000个最大的数，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。面试题目：如何在10亿个整数中找出前1000个最大的数。我们知道排序算法有很多：冒泡算法：通过两层for循环，外层第一次循环找到数组中最大的元素放置在倒数第一个位置，第二次循环找到第二大的元素放置在倒数第二个位置。。。循环N次就可以找到TopN。
缺点：冒泡排序内层循环需要大量交换元素。复杂度 香港云主机介于O(n)和O(n^2)之间。快速排序：选一个基准元素，每次排序可以将这个基准元素搁置在正确的位置，左边都是比基准小的元素，右边都是比基准大的元素从而将数组分成左右两部分，分而治之。TopN问题也同样如此，选择一个基准元素并通过快速排序将基准元素搁置在正确的位置，如果左边的元素个数小于1000，那么继续从基准右边排序，如果左边元素个数大于1000，那么从基准左边排序，直到基准的位置正好在1000，结束。
缺点：第一次排序复杂度是O(n),第二次排序复杂度是O(n/2),第三次排序复杂度是O(n/4)….文件存储，分而治之:将比基准小的元素存储在txt1中，比基准大的文件存储在txt2中，然后通过类似方法二的形式，最后求出TopN。缺点：磁盘读取，写入次数过多。MapReduce:单机内存和性能确实受限，那么我们可以将10亿个分段存储在不同的机器上，每台机器计算各自的TopN，最后汇总。
缺点：空间换时间。在内存中维护一个长度为N的数组，根据堆的性质，每一个节点都比他的左右子节点小，先取出前N个数并构建小顶堆，然后将所有数据与堆顶比较大小，如果比堆顶小就直接丢弃，如果比堆顶大则替换堆顶，并且重新构建这个堆。 构建小顶堆的过程：先要找到最后一个非叶子节点，数组的长度为6，那么最后一个非叶子节点就是：长度/2-1，也就是6/2-1=2，然后下一步就是比较该节点值和它的左右节点值，如果该节点大于其左右子树的值就交换（意思就是将最小的值放到该节点）。如果该节点不是叶子结点，则递归这一过程，直到这个节点变成叶子节点。具体执行代码如下：看完上述内容，你们掌握如何用TopN算法在10亿个整数中找出前1000个最大的数的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注开发云行业资讯频道，感谢各位的阅读！
本篇内容主要讲解“C#中单例模式的实现代码”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C#中单例模式的实现代码”吧!饿汉式实现很简单，在静态构造函数中立即进行实例化：注意，为了确保单例性，需要使用 readonl…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
