面试题：如何 O(n) 的复杂度内筛选 60 亿人的身高

[Daredevil0086]

完整的题目差不多是这样的：

现在有一个文件 a.txt ，其中放的内容就是 60 亿人的身高，每个身高数据都保证是以.0 或者.5 结尾的（比如说 180.0 ，175.5 ）；现在请筛选出其中前 1000 高的数据；

要求时间复杂度是 o(n);

面试官说这玩意不是一个单纯的算法，身高数据可以做点文章……但到最后还是没想出来………………有没有高智商 V 友可以解答一下

感谢各位高智商 V 友的各种回答和意见，感觉基本确定了答案就是 1L 和 6L 的方案就是面试官想要的~~~

总之，千言万语汇成一句话：

家人们，爱你啾咪❤，mua~~

[fengjianxinghun]

人类的身高是有上下限的，正确点说就是 0.5-3 米之间，而且他保证了是.0/.5 结尾，就减少到一个更小的数值集合，这样想你是不是就懂了?

[lolizeppelin]

遍历的时候超过 2 米的.....或者低一点 1.95

[iamzuoxinyu]

桶排序

[Nugine0]

基数排序

[Daredevil0086]

@iamzuoxinyu 桶排序最差能到 O(n^2)吧，不在 O(n)内

[leogm9408leo]

数据是以.0 或者.5 结尾，意味着这是个有范围的离散数据而不是连续数据。假设人类的身高区间是 10 厘米-250 厘米，间距 0.5 厘米，其实也就（ 250-10 ）*2=480 个。作 480 个数据桶，遍历一遍就可以把 60 亿数据都放到这 480 个数据桶里，然后取不为空的最大身高值的桶里的数据即可

[devfeng]

https://leetcode.cn/problems/kth-largest-element-in-an-array/ 第 k 个最大元素，思路是一样的

[edward1987]

前 1000 高的，又不是所有都排序，用一个数组存当前最高的 1000 个，遍历一遍，遇到更高的就替换数组内容就好了啊。复杂度就是 0(n)

[Daredevil0086]

@fengjianxinghun 额，即使是不看结尾小数，好像稳定在 O(n)内的排序算法也没有吧

[githmb]

一个容量为 1000 的向量，60 亿数据依次往里面塞，每塞一次做个排序

[Daredevil0086]

@devfeng 哦哦哦哦，那我算答对了？我用的是快排那个…………………………但是还是没太理解怎么用身高这点来做优化

[insanny]

同意 6 楼的思路

[raycool]

堆排序

[sun1991]

开一个 HashMap, 把可能的身高数据以 key 的形式预先插入. 然后遍历集合, 插入 HashMap. 最后以身高为 key, 从高到底, 从 HashMap 拿数据, 凑满 1000 即可.

[FACEB00K]

不考虑身高数据，构建 size 为 1000 的最小堆；
如果考虑升高数据，用一个数组统计身高就能解决吧，数组下标和身高有映射关系，而且身高范围是固定的；最后逆序遍历数组

[Daredevil0086]

@edward1987 那是平均复杂度吧，面试官这么说的……

[coyoteer]

计数排序？

[picone]

@FACEB00K 用了堆就不是 O(n) 了

[codingbody]

@edward1987 #8
@raycool #13 这是 O(nlogk) 吧

[Daredevil0086]

兄弟们，面试官好像想考察的是怎么用身高做文章，我最终交上去的答案是 7 楼贴的 leetcode 题目的快排版本答案；

感觉这题，好像跟算法没关系~~~~属于动脑子的那种

[UnknoownUser]

// (3-1.9)/0.05=22
int counter[22];

[UnknoownUser]

@UnknoownUser 时间复杂度为 O(n)就只能每个数据都访问一次咯，大致猜测一下前 1000 高的人类应该在 1.9-3.0m 之间，所以遍历一次用计数器把它们都记录下来

[xuanbg]

6 楼正解

[FACEB00K]

@codingbody
@picone k 不是一个常数吗，这里是 1000

[tuxz]

线性直方图

[icyalala]

"前 1000 高的数据" 要去重吗?

[picone]

@FACEB00K #24 其实是 n 次 大小为 1000 的堆插入，应该是 n * log2(1000)

[lymanlai]

感觉在写回字的几种写法。。

[mxT52CRuqR6o5]

我很怀疑面试官是不是自以为是的认为桶排序算是一种优化

[IwfWcf]

面试官都提示得那么明显了，就是在提示桶的数量很少啊……

[FACEB00K]

@picone 一般是像你这么算的，每次都是和堆顶比较，比堆顶大的才删除堆顶，再插入；如果比堆顶小，直接就 pass 了，算法复杂度就是 O(nlogk)；但是身高应该是符合正态分布的，前 1000 名身高可能只占百分之零点零几，甚至更少，60 亿数据中，基本上没多少次插入

[tyler1128]

受 6 楼启发，480 个桶，先取 1000 个放入各自的桶内，然后淘汰掉数量不为 0 的最小的桶后面的所有桶，初始化一个计数器，初始值为最小的桶内令牌的数量。后面再次取数时，如果小于最小的桶，直接丢弃（节省哈希时间），如果这个数是此时场上最小的桶，则计数器加 1 ，如果不是最小的桶，计数器-1 ，当计数器为 0 时，丢弃最小的桶，重新排序找到新的最小的桶，计数器设置为新的最小的桶内令牌数量。重复该操作，直到遍历完 60 亿数，此时剩下的就是最大的 1000 个（数量可能会超过 1000 ，因为最小的桶可能有很多相同的值）。

[picone]

@FACEB00K #31 题目没有这个假设，这样不太合适。 即使有这个假设，按照二八分布，顶多也只能是 0.8n + 0.2 * n * log2(1000)，也不完全是 O(n)

[HashV2]

嗯 应该就是先考察一个 topk 的算法问题，然后主要让你谈这个数据可以干嘛

60 亿是一个全球人数级别的数据，但是我也想不出这个数据到底可以做啥文章😂

[UIXX]

也不考虑 O(n)，我们的期望是 [一轮遍历+尽可能少的空间] 达到筛选目的。

在现实中处理此类问题需要数据清洗并建模，简单地，我们需要预估身高分布，比如是全随机分布还是正态分布？

无论是哪一种，我们都能估算出一个合适的身高范围，如果用桶，这个范围会使桶的数量大大减少。

[wanguorui123]

分别创建：List ，最大变量 A ，最小变量 B ，遍历 txt 数据时每次和最大变量 A 和最小变量 B 对比，将最大数据计入即可，然后加入 List ，让 List 始终保持 1000 个以内即可，遍历完成后对 List 快速排序既可以，非常简答

[akira]

这样 身高数据 是有限的啊。。统计出 每个高度的人数，然后从上往下拿够 1000 个

[pkoukk]

@wanguorui123
不行的。假如数据集中的第一个值是 max,第二个值是 min ，那 list 跑到最后只有两个元素。

[e7]

1L 就已经给出标准答案了，任何带比较的都超过 O(n)了，btw：面试官挺无聊的

[mmuggle]

2000cm 不够高是吧？直接 O(1) 🤣

[darkengine]

确实是基数排序，只不过基用的是人类的身高，例如 355.0, 354.5 。

[8355]

1 楼说的是对的,这是常识问题加基本方案解决.
其他说 60 亿次遍历或者比较的方案最大的问题就是存储 60 亿的问题必然是不符合出题者的意图的.
我猜应该就是要问布隆过滤器吧.

[cclin]

打开算法导论，翻到 112 页，得到一个最差时间复杂度 O(n) 的算法
顺便 60 亿个数字在现在的硬件上不算一个很大的规模
鉴定为题出得不行

[iOCZ]

topK 算法挺常见的。用优先级队列构造 1000 个容量的小根堆，比堆顶小的舍弃，比堆顶大的进入。这个复杂度是 O(n*log2n)。要达到 o(n)的话，得使用空间复杂度更高的，类似计数排序。因为身高肯定是一个有限的数据点集，可以简单通过计数来实现获取前 1000 的数据。

[yzbythesea]

经典堆排序问题

时间复杂度说 O(nlogk) 是错误的、说明不理解复杂度一说。n 和 k 不在一个量级可把 logk 视为常量。

[XiLingHost]

这不是很典型的计数排序场景吗......

[NoOneNoBody]

身高符合正态分布，六百万分之一只考虑>2m 就够了
算法我是文盲，pass

[ytmsdy]

o(n)的复杂度应该不难吧。只需要前 1000 ，又不用全部数据排序。
搞一个长度为 1000 的数组，搞一个插入排序，如果值大于 1000 中的最小值，那就插入，并把最后那个元素给删掉。
其实也就是 1000*o(n)的复杂度，也就 O(n)的复杂度

[iOCZ]

@yzbythesea 你说得对，我这个复杂度写错了。

[geelaw]

O(n) 和 o(n) 是不同的意思，后者是前者的真子集。更不能写成 0(n)，最后这个东西只能被理解为零乘 n ，也就是 0 。

另外问题的表述不清楚：n 是什么？

合理的表述如下：文件里有 n 个人的身高（厘米）且每个数据都是 整数.0 或者 整数.5 ，求最高的 1000 个人的身高。要求算法是 O(n) 时间的。

60 亿和 1000 都是常数，原来表述下的问题可以在 O(1) 时间内解决。

[ershierdu]

@geelaw
想起了去年找实习的面试，一道字符串相关的题，大意是给定一个字符串，找出其中第一个“只出现了一次的字符”的下标。我用 HashMap 做的，在已经明确字符串只包含英文字母的前提下，面试官非说最坏时间复杂度是 O(nlog n)，因为底层的红黑树最坏就是 O(n logn)…

[ershierdu]

@ershierdu
typo：底层红黑树最坏是 O(log n)

[wudicgi]

用 hashtable, key 为身高, value 为该身高出现的次数
最后取出 hashtable 的 key, 按从大到小的顺序排序，再逐个看 value, 输出 key 的值直到 value 加起来 >= 1000
这样可行不？

[sylxjtu]

可以参考《编程珠玑》第一章，讲得非常清楚

[tiandao84]

好久没做题我也知道😯遍历一遍构建大顶堆，复杂度 O(n+LogN)

[zhy0216]

@tiandao84 对的
而且不需要“每个身高数据都保证是以.0 或者.5 结尾的”的条件

[20015jjw]

bucket sort 例题啊 cs61b…

[veike]

@leogm9408leo 兄弟有博客吗，关注一波

[Knuth]

@20015jjw 果然湾区

[xxfye]

首先，1k 的排序可以视作常数，剩下的看你们发挥了。

[Badlink]

60 亿，假设每个身高浮点数表示的话是 8 字节，大概 5 * 10^10 B = 50G 。如果内存放不下的话就放 50 个文件，每次对一个文件桶排序，取前 1000 个，最后对这 50 个文件共 50000 个数再桶排序一次

[oamu]

@picone 时间复杂度是对于输入来说的，在这个问题里，输入是 60 亿的身高数据，用一个大小为 1000 的堆进行排序取前 1000 大的数据，这个 1000 就是个常数，总的时间复杂度就是 O(n)。

[tyrantZhao]

位图

[k9982874]

这题内存没限制的情况下不是 for loop 一遍就出结果了吗

[mingl0280]

先来一个长度 480 的 int 数组，然后身高*2%480 到桶里，最后从前往后输出不为零的项就完事了

[mingl0280]

如果要剪枝还可以直接滤掉身高小于两米的……

[hxysnail]

用一个规模为 1000 的最小堆，然后遍历数据，如果比堆顶大，就替换堆顶，再调整一下堆结构。遍历完好，堆里面的数据就是前 1000 。

由于 1000 是固定的，每次维护最小堆的时间可以认为是一个常量 k ，这样一来，时间复杂度为 O(kN)，等价与 O(N)。
这个方法适用于任何数据，从 N 个数据中取最大或最小的 n 个，只要 n 远小于 N 就行。

[bianhui]

60 亿人任何一个人的身高都不止一个人，只需找到最高的人，然后输出一千次就行了

[WngShhng]

不是吧，如果要在更小的范围内搜索，前提是数据是有序的，如果数据经过排序，复杂度就达不到 O(n) 的要求。不考虑内存的话，遍历一遍，将 top 高的数据记录在一个列表里，同时记录这个列表的最小值，然后如果遇到高于这个最小值的或者列表还没满，这个时候把数据塞到列表里，同时更新列表的最小值，即可。这样对于列表不需要进行额外的排序浪费时间复杂度，这样才可以达到 O(n) 的要求。如果考虑实际情况，这个问题难度在于如何分块读取数据，以保证读取数据到内存之后，内存不会爆掉，所以，.0 或者 0.5 可能是分块读取的依据（当然你应该问一下数据在文本中是如何存储的

[magicyao]

很明显的桶排，然后取 1000 个，1000 是常数可以不计入复杂度中

[summerLast]

可以用桶 比如 200cm 对应第 4000 个桶 然后每个桶里这个身高对应的人数，找到满足条件的最大的几个桶的身高

下一步就是如何用并发等提高入桶的统计速度，如先 xx 线程处理入桶，然后 xx 线程合并桶 几次迭代之后就有了上述的统计

[loryyang]

这种都老题了，其实没啥意思。知道解法会觉得很简单，不知道的，咋可能在面试的时候想出来。所以我面试从不出这种题目，不公平，没有筛选意义

[limitsy]

1 楼的意思应该也是哈希表吧？把身高上下限定为 0-3 米 转换为毫米 0-3000 ，然后可以建立一个长度为 3000 的整型数组（其实如果小数都是.0/.5 ，都不需要这么大的数组）。那么遍历身高，只需要把 arr[身高 * 10] ++ 。最后再从数组最大开始反向遍历取出前 1000 就可以了。

[picone]

@oamu 按照你这个说法，堆的大小只要是常数就不会影响时间复杂度？堆大小是 1000000 呢？

[leeraya]

典型的 topk 问题

[enson110]

贴一个 GPT4 给的答案，是的真的强：

```
如果你需要一个 O(n) 时间复杂度的解决方案，那么可以使用一个叫 "桶排序" 的技术。"桶排序" 是一种可以在线性时间内完成的排序算法，但是这需要对输入数据有一些特定的假设。

根据你的问题描述，人的身高是以 0.5 的单位进行记录的。我们可以假设一个可能的范围，比如说从 0.0 到 300.0 。然后我们创建 600 个桶（一个桶代表 0.5 的身高），每个桶都对应了一个可能的身高。然后遍历所有的数据，根据身高将人放到对应的桶里。这一步的时间复杂度为 O(n)。

接下来，我们可以从最高的桶开始，检查每个桶里有多少人。然后从这个桶开始向下找，直到找到 1000 个人。这一步的时间复杂度为 O(1)，因为桶的数量是固定的。

这样，整个算法的时间复杂度为 O(n)。需要注意的是，这种算法的效率取决于我们的假设是否准确，以及数据是否均匀分布。如果数据的分布很不均匀，桶排序的效率就会降低。

这是一个基本的桶排序应用。如果需要处理更复杂的情况，比如说数据的范围不确定，或者桶的数量太多等，我们可能需要使用其他的技巧，比如说动态地创建桶等。但是基于你的问题描述，这个基本的方法应该就可以工作得很好。
```

[fdd92]

@picone 时间复杂度讨论的是总时间随项的增加而增加的情况，所以堆大小是常数就不影响时间复杂度。如果堆大小不是常数，那时间复杂度就是 O(n log m)。

[oamu]

@picone #74 要比较前 1000 和前 1000000 ， 实际上是把 1000 当作输入，那它也就不是常数了，用堆排序时间复杂度是最坏就是 O(n logk)；但按照原题的条件和常识，可以知道可能的身高数量是有限的，且与数据规模（输入）无关，可以看成一个常数，每个身高最多插入堆 k 次，那么用堆排序最坏的时间复杂度应该是 O(n + k log k)。之前默认将 1000 看作常数是考虑不周。

[jameskongawork]

o(1) 人均 180

[buxudashi]

这个，结果集其实是个链表。一个一个插入得了。

[身高 2 米 4] =N 个人
[身高 2 米 35] =M 个人

[wengyanbin]

人类的身高应该也是满足正态分布的，前 1000 占据 60 亿的比例，大体可以划出一个区间范围，作为过滤条件可以大幅度过滤掉不符合的

[jixiangqd]

这感觉像是脑筋急转弯。。。不过问题也许也是有些许应用价值的，可以作为种思路学习下

[iX8NEGGn]

类似词频统计，四层 trie 就能解决 ，第一层 0~3 （人的身高不会超过 3 米），第二层 0~9 ，第三层 0~9 ，第四层只有 0 和 5 ，每个 trie 节点有一个 count ，遍历一边 60 亿人的身高，每种身高有多少人就全得到了

[wangritian]

6L 并不是正解，8L 才是

[zengmingyang96]

bitmap

[wwbfred]

如果题目说身高都是整数，那么很容易就会想到统计每个身高对应的人数。出现半整数不改变题目本质，但具有迷惑性，让人更难想到最简单的方法。

[mrzhangrb]

压根不用排序吧， 用哈希 key 为身高，val 为这个身高出现的次数， 遍历一遍， 从最高身高向下取 1000 个