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

查看 690|回复 81
Badlink   
@20015jjw 果然湾区
oamu   
首先,1k 的排序可以视作常数,剩下的看你们发挥了。
tyrantZhao   
60 亿,假设每个身高浮点数表示的话是 8 字节,大概 5 * 10^10 B = 50G 。如果内存放不下的话就放 50 个文件,每次对一个文件桶排序,取前 1000 个,最后对这 50 个文件共 50000 个数再桶排序一次
k9982874   
@picone 时间复杂度是对于输入来说的,在这个问题里,输入是 60 亿的身高数据,用一个大小为 1000 的堆进行排序取前 1000 大的数据,这个 1000 就是个常数,总的时间复杂度就是 O(n)。
mingl0280   
位图
mingl0280   
这题内存没限制的情况下不是 for loop 一遍就出结果了吗
hxysnail   
先来一个长度 480 的 int 数组,然后身高*2%480 到桶里,最后从前往后输出不为零的项就完事了
bianhui   
如果要剪枝还可以直接滤掉身高小于两米的……
WngShhng   
用一个规模为 1000 的最小堆,然后遍历数据,如果比堆顶大,就替换堆顶,再调整一下堆结构。遍历完好,堆里面的数据就是前 1000 。
由于 1000 是固定的,每次维护最小堆的时间可以认为是一个常量 k ,这样一来,时间复杂度为 O(kN),等价与 O(N)。
这个方法适用于任何数据,从 N 个数据中取最大或最小的 n 个,只要 n 远小于 N 就行。
magicyao   
60 亿人任何一个人的身高都不止一个人,只需找到最高的人,然后输出一千次就行了
您需要登录后才可以回帖 登录 | 立即注册

返回顶部