首页
论坛
Yoo趣儿
›
Geek
›
程序员
›
面试题:如何 O(n) 的复杂度内筛选 60 亿人的身高 ...
面试题:如何 O(n) 的复杂度内筛选 60 亿人的身高
查看
1154
|
回复
81
githmb
2023-5-30 15:13:49
@fengjianxinghun 额,即使是不看结尾小数,好像稳定在 O(n)内的排序算法也没有吧
Daredevil0086
OP
2023-5-30 15:14:32
一个容量为 1000 的向量,60 亿数据依次往里面塞,每塞一次做个排序
insanny
2023-5-30 15:15:09
@devfeng 哦哦哦哦,那我算答对了?我用的是快排那个…………………………但是还是没太理解怎么用身高这点来做优化
raycool
2023-5-30 15:15:45
同意 6 楼的思路
sun1991
2023-5-30 15:16:16
堆排序
FACEB00K
2023-5-30 15:17:01
开一个 HashMap, 把可能的身高数据以 key 的形式预先插入. 然后遍历集合, 插入 HashMap. 最后以身高为 key, 从高到底, 从 HashMap 拿数据, 凑满 1000 即可.
Daredevil0086
OP
2023-5-30 15:17:58
不考虑身高数据,构建 size 为 1000 的最小堆;
如果考虑升高数据,用一个数组统计身高就能解决吧,数组下标和身高有映射关系,而且身高范围是固定的;最后逆序遍历数组
coyoteer
2023-5-30 15:18:49
@edward1987 那是平均复杂度吧,面试官这么说的……
picone
2023-5-30 15:19:45
计数排序?
codingbody
2023-5-30 15:20:34
@FACEB00K 用了堆就不是 O(n) 了
下一页 »
1
2
3
4
5
6
7
8
9
/ 9 页
下一页
返回列表
您需要登录后才可以回帖
登录
|
立即注册
发表回复
浏览过的版块
IOS/macOS
搜索
热门主题
ioio事件是什么鬼?
养老贷又来了,贷贷相传啊
今天要撸2次
好评有礼给的是红包还是优惠卷
现在干啥都太难了,珍惜吧
淘宝现在也好难搞啊
现在的ai能生产图文结合的内容吗
周固固突然发飙了,谁惹他了呢?吃光群众等
怎么吵架了啊
老坛们看过来,周固固同志狂撒金币。折射一
热门板块
问与答
分享发现
分享创造
奇思妙想
分享邀请码
商业推广
优惠信息
Python
PHP
Java
JavaScript
Node.js
Go语言
C++
HTML
公告
网站帮助 - Yoo趣儿
2022-03-27
我们的愿景
2022-03-27
在 Yoo趣儿 投放广告
2022-03-27
Yoo趣儿网站用户应遵守规则
2022-03-24
返回顶部