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

[Daredevil0086]

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

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

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

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

[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) 🤣