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

[Daredevil0086]

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

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

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

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

[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 题目的快排版本答案；

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