如何在一亿个数当中找到最大的10000个数？

拿到这道题，马上就会想到的方法是建立一个数组把1亿个数装起来，然后用for循环遍历这个数组，找出最大的1万个数来。原因很简单，如果要找最大的那个数，就是这样解决的；而找最大的一万个数，只是重复一万遍。

这个解法类似于选择排序，一次将一个正确解放在合适的位置，重复一万次，所以时间复杂度为O(n *m)，如果你愿意去实现一下，会发现不等个几十分钟是不会出结果的。

在日常生活中，我们经常会遇到排序问题：

在打扑克牌的时候，原本拿到手上的牌是乱序的，我们会按照自己喜好的顺序一张一张排好手上的牌，最后看起来是顺眼的。

摄影师给毕业的同学们拍照片，要求同学们站好队形，然后要求中间高，两边低的方式排队。如果摄影师发现某个同学的高度跟旁边的同学不协调，这个同学必须马上调整自己的位置，最后是一派整齐的景象：

经常泡图书馆的泡友，会发现有很多志愿者会帮忙整理图书位置。每一本书的书背上面都有一张标签，书架上的图书需要按照标签上的编号排好顺序，这样泡友才能快速找到想要的图书。

这些例子就是排序问题了。排序问题不仅在生活中常见，在IT届也常见。据说，某科技公司在做一个项目时遭遇大量排序问题，运算速度奇慢，项目经理非常头痛，为招收能制伏排序问题的人才，干脆总结成了一道题目：

如何在一亿个数当中找到最大的10000个数？

我们不仅要考虑，计算机能够如何找到这10000个最大的数，更重要的是找到这10000个数的时间越短越好。

方法一：重复寻找法

我们可以先用最直观的方式来做这道题目，起个名字叫重复寻找法：

第1步：我们先在这一亿个数当中，寻找到最大的那个数字，把它记录下来。

第2步：从这一亿个数字中，剔除这个最大的数字。

第3步：重复执行第1步和第2步，直至记录下来10000个数字。记录下来的结果即为所求。

以挑苹果为例，重复寻找法就好比我们在苹果堆中挑苹果的时候，先在所有苹果里面挑出最好的一个，然后继续在剩余苹果里面再挑出最好的一个……如此类推。

怎么找到最好的苹果？那必须拿着某个苹果，对比一遍所有苹果，如果发现有更好的苹果，把好的苹果拿在手上，把次好的苹果放下，直至对比完所有的苹果后，手上拿着的就是最好的苹果。

重复寻找法，就好比在苹果堆中不断挑最大最好看的苹果到自己的篮子里

为了方便讨论起见，我们设n = 1亿

我们知道，求n个数最大值的比较次数为n，求最大值的过程需要执行10000次，因此，重复寻找法的总比较次数为：

10000 × n

虽然这个问题有答案了，但是心里貌似有一些遗憾，不知道大家感受到了没？

其实，遍历10000次，这个次数有点多，为什么不可以遍历1次就得到结果呢？

方法二：局部淘汰法

实际上是可以的，还有一个能够一步到位的方法，叫做局部淘汰法：

第1步：先创建一个数组，保存这1亿个数字中的前10000个数字，计算数组的最小数字。

第2步：遍历剩下的数字。如果遍历到某个数 A 大于数组的最小数字，那么则用 A 替换掉数组的最小数字。并重新计算数组的最小数字。

第3步：遍历完成后，数组内的数字即为所求。

以打麻将为例，一开始我们拿了n个牌，局部淘汰法类似我们在打麻将过程中，如果摸到一个比自己手上最坏的牌要好的牌，就打出自己手上最坏的牌……如此类推，使得胜利的概率不断增大。

局部淘汰法，可以类比打麻将的过程，不断更换手上的牌，使得胜利的概率越来越大

这样，遍历1次就能得到最后的结果了。总比较次数如何呢？

最好的情况是，如果这1亿个数字刚好已经是降序排列，那么前10000个数字就是结果，只需要进行1次最小值的计算（比较次数为 1 × 10000），9999万次最小值的比较（次数向上近似为 n）。

最坏的情况是，如果这1亿个数字刚好已经是升序排列，那么直到最后的10000个数字才是最终结果，因此需要进行9999万次最小值的计算（比较次数为 n × 10000），9999万次最小值的比较（次数向上近似为 n ）

因此，平均的情况是，要算5000万次最小值（比较次数为 1/2 × n × 10000），要算9999万次最小值比较（次数向上近似为 n ，因此总比较次数近似为 ：

1/2 × n × 10000 = 5000 × n

总比较次数下降了一半，这个优化有点用。

但是……大家有没有觉得这个方法还有优化空间？

方法三：最小堆维护法

这个问题嘛……事实上是有的。这个方法能够大幅度降低总比较次数，称之为最小堆维护法：

第1步：先利用前10000个数字，搭建一个元素个数为1万的最小堆。

有同学可能会问，什么叫做最小堆呢？在这里解释一下：

首先，什么是堆?

在计算机领域中，堆这个概念与生活中的有一点点类似，一般的堆也是上面窄下面宽的结构。堆结构，非常类似圆木堆放的结构，充满大自然的气息。

堆结构，可能源自圆木木堆的灵感

堆（heap）是一种基于树（tree）的特殊的数据结构。堆有两种形式，分别是最大堆（max heap）和最小堆（min heap）。在堆顶的节点则被称为根节点。

我们关心最小堆就可以了。最小堆中，如果节点 A 是节点 B 的父节点，节点 A 中的键值必定小于或者等于节点 B 中的键值。根节点是堆的最小值。

堆的形式有非常多，不过堆的最常见实现形式是二叉堆（binary heap），最小二叉堆一般也是被直接简称为最小堆，因此我们只需要理解二叉堆即可。我们可以画一个最小二叉堆的例子出来感受一下：

一个最小堆示例

对图中的最小堆分析，一共有三层圆圈，称之为节点，每一个上层的节点都连着下层的两个节点，而且上层节点的键值均比下层的两个节点的键值要小。这个就是最小堆的特征。

我们来继续做题吧：

第2步：遍历剩下的数字，与最小堆的根元素键值进行对比。如果遍历到某个数确实大于根元素的键值，则替换根元素的键值，并进行堆调整。

第3步：遍历完成后，最小堆当中的所有元素对应的数值即为所求。

刚刚说明了堆调整时间，最坏情况下调整时间为 log2 10000。同时要进行9999万次最小值比较（次数向上近似为 n）。因此上述步骤的比较次数最多为：

n × log2 10000

总比较次数进一步下降了5000 ÷ 14 > 350倍，这个优化确实漂亮。

比赛流程

比赛名称：

有方AI萌新挑战赛

Embark AI Meng Xin Challenge

比赛赛题：

5 道编程题

比赛时间：

北京时间02月12日10:00 比赛试题开放

北京时间02月14日10:00 停止作答

各位有48小时的挑战时间来完成这5道编程题，需要抓紧哦 ~

参赛对象：

所有正在【萌新学习群】学习【AI初探：数据科学】课程的学生都有资格参与

参赛形式：

登录「有方 AI 云」即可获取题目开始挑战

比赛规则：

正确率优先。在正确率相同的情况下，以时间优先为标准

是不是很简单！只要你参与，动动你聪明的小脑袋，就能够把你的智慧转换成压岁钱~

而且还是真！金！白！银！想一想，喜欢的都能买买买了呢！

那，我们的奖金池又是什么样子的呢！

如何加入「萌新学习群」？

加入

流程

step 2

获得免费「AI素养测评」，完成测试后提交

step 3

获得「AI素养测评报告」，了解学习路径

step 4

由小助手拉入「萌新学习群」

step 5

开始AI学习之路！