励志当最强课代表的我来给大家总结总结👍👍👍

大厂面试题】如何在一亿个数中找出最大的1万个数？

总结:

一、软件应用的问题😃

二、软件应用的看法😃

三、软件应用的结论😃

一、软件应用的问题😃❓

✨大厂面试题】如何在一亿个数中找出最大的1万个数？

二、软件应用的看法😃

✨1.快速排序法

最先想到的大概就是使用快速排序算法，遍历所有数据,进行排序后，取出最前面的10000个，时间复杂度为0 (nlogn)，1个数字按照4字节来算，最多占用40口MB。一般来说我们的机器内存是可以撑住的，但是这种主要是效率不高，我们只要前1 000 0个，在排序的过程中,我们会浪费很多时间去做无用功。

✨2.淘汰法

先用一个list保存前10000个数字，然后遍历剩下的数字，如果某一个数字比容器中的数字大，那么删除掉容器中的數据进行替换，假如说后面的数字正好都比前面的小，那么容器中的就是最大的。时间复杂度为0 (n+m^2 )

✨3.分治法

将1亿个数据分成10000份，每份10000万个数据，用多线程然后使用快速排序来找到每份数据中最大的10000个，最后在剩下的数据里面快速排序找出最大的10000个。这样我们的效率会很高，提升了CPU的利用率。相比第一种方法，我们提高了100倍的速度。

✨4.最小堆算法

首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为0(mlogm)(m为數组的大小即为1口000)，然后遍历后续的数字，并于堆顶( 最小)数字进行比较。如果比最小的數小，则继续读取后续数字;如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为0 (nmlogm)，空间复杂度是I oooo(常数)

三、软件应用的结论😃

✨学习以上内容