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

查看 686|回复 81
IwfWcf   
我很怀疑面试官是不是自以为是的认为桶排序算是一种优化
FACEB00K   
面试官都提示得那么明显了,就是在提示桶的数量很少啊……
tyler1128   
@picone 一般是像你这么算的,每次都是和堆顶比较,比堆顶大的才删除堆顶,再插入;如果比堆顶小,直接就 pass 了,算法复杂度就是 O(nlogk);但是身高应该是符合正态分布的,前 1000 名身高可能只占百分之零点零几,甚至更少,60 亿数据中,基本上没多少次插入
picone   
受 6 楼启发,480 个桶,先取 1000 个放入各自的桶内,然后淘汰掉数量不为 0 的最小的桶后面的所有桶,初始化一个计数器,初始值为最小的桶内令牌的数量。后面再次取数时,如果小于最小的桶,直接丢弃(节省哈希时间),如果这个数是此时场上最小的桶,则计数器加 1 ,如果不是最小的桶,计数器-1 ,当计数器为 0 时,丢弃最小的桶,重新排序找到新的最小的桶,计数器设置为新的最小的桶内令牌数量。重复该操作,直到遍历完 60 亿数,此时剩下的就是最大的 1000 个(数量可能会超过 1000 ,因为最小的桶可能有很多相同的值)。
HashV2   
@FACEB00K #31 题目没有这个假设,这样不太合适。 即使有这个假设,按照二八分布,顶多也只能是 0.8n + 0.2 * n * log2(1000),也不完全是 O(n)
UIXX   
嗯 应该就是先考察一个 topk 的算法问题,然后主要让你谈这个数据可以干嘛
60 亿是一个全球人数级别的数据,但是我也想不出这个数据到底可以做啥文章😂
wanguorui123   
也不考虑 O(n),我们的期望是 [一轮遍历+尽可能少的空间] 达到筛选目的。
在现实中处理此类问题需要数据清洗并建模,简单地,我们需要预估身高分布,比如是全随机分布还是正态分布?
无论是哪一种,我们都能估算出一个合适的身高范围,如果用桶,这个范围会使桶的数量大大减少。
akira   
分别创建:List ,最大变量 A ,最小变量 B ,遍历 txt 数据时每次和最大变量 A 和最小变量 B 对比,将最大数据计入即可,然后加入 List ,让 List 始终保持 1000 个以内即可,遍历完成后对 List 快速排序既可以,非常简答
pkoukk   
这样 身高数据 是有限的啊。。统计出 每个高度的人数,然后从上往下拿够 1000 个
mmuggle   
@wanguorui123
不行的。假如数据集中的第一个值是 max,第二个值是 min ,那 list 跑到最后只有两个元素。
您需要登录后才可以回帖 登录 | 立即注册

返回顶部