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

[Daredevil0086]

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

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

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

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

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