Yoo趣儿

Yoo趣儿 › Geek › 程序员 › 面试题：如何 O(n) 的复杂度内筛选 60 亿人的身高 ...

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

查看 1269|回复 81
githmb   
@fengjianxinghun 额，即使是不看结尾小数，好像稳定在 O(n)内的排序算法也没有吧
Daredevil0086
OP
  
一个容量为 1000 的向量，60 亿数据依次往里面塞，每塞一次做个排序
insanny   
@devfeng 哦哦哦哦，那我算答对了？我用的是快排那个…………………………但是还是没太理解怎么用身高这点来做优化
raycool   
同意 6 楼的思路
sun1991   
堆排序
FACEB00K   
开一个 HashMap, 把可能的身高数据以 key 的形式预先插入. 然后遍历集合, 插入 HashMap. 最后以身高为 key, 从高到底, 从 HashMap 拿数据, 凑满 1000 即可.
Daredevil0086
OP
  
不考虑身高数据，构建 size 为 1000 的最小堆；
如果考虑升高数据，用一个数组统计身高就能解决吧，数组下标和身高有映射关系，而且身高范围是固定的；最后逆序遍历数组
coyoteer   
@edward1987 那是平均复杂度吧，面试官这么说的……
picone   
计数排序？
codingbody   
@FACEB00K 用了堆就不是 O(n) 了
下一页 »
123456789下一页
返回列表
您需要登录后才可以回帖 登录 | 立即注册

AD1

热门主题

热门板块

问与答分享发现分享创造奇思妙想分享邀请码商业推广优惠信息PythonPHPJavaJavaScriptNode.jsGo语言C++HTML

公告

标签|小黑屋|Yoo趣儿

GMT+8, 2025-11-28 10:07 , Processed in 0.012647 second(s), 11 queries , Gzip On, MemCached On.

Powered by Discuz! X3.2

The happiest thing in the world is to strive for an ideal.

返回顶部