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

查看 683|回复 81
darkengine   
1L 就已经给出标准答案了,任何带比较的都超过 O(n)了,btw:面试官挺无聊的
8355   
2000cm 不够高是吧?直接 O(1) 🤣
cclin   
确实是基数排序,只不过基用的是人类的身高,例如 355.0, 354.5 。
iOCZ   
1 楼说的是对的,这是常识问题加基本方案解决.
其他说 60 亿次遍历或者比较的方案最大的问题就是存储 60 亿的问题必然是不符合出题者的意图的.
我猜应该就是要问布隆过滤器吧.
yzbythesea   
打开算法导论,翻到 112 页,得到一个最差时间复杂度 O(n) 的算法
顺便 60 亿个数字在现在的硬件上不算一个很大的规模
鉴定为题出得不行
XiLingHost   
topK 算法挺常见的。用优先级队列构造 1000 个容量的小根堆,比堆顶小的舍弃,比堆顶大的进入。这个复杂度是 O(n*log2n)。要达到 o(n)的话,得使用空间复杂度更高的,类似计数排序。因为身高肯定是一个有限的数据点集,可以简单通过计数来实现获取前 1000 的数据。
NoOneNoBody   
经典堆排序问题
时间复杂度说 O(nlogk) 是错误的、说明不理解复杂度一说。n 和 k 不在一个量级可把 logk 视为常量。
ytmsdy   
这不是很典型的计数排序场景吗......
iOCZ   
身高符合正态分布,六百万分之一只考虑>2m 就够了
算法我是文盲,pass
geelaw   
o(n)的复杂度应该不难吧。只需要前 1000 ,又不用全部数据排序。
搞一个长度为 1000 的数组,搞一个插入排序,如果值大于 1000 中的最小值,那就插入,并把最后那个元素给删掉。
其实也就是 1000*o(n)的复杂度,也就 O(n)的复杂度
您需要登录后才可以回帖 登录 | 立即注册

返回顶部