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

[Daredevil0086]

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

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

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

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

[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 个人