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

[Daredevil0086]

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

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

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

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

[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 果然湾区

[NXzCH8fP20468ML5]

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