首页
论坛
Yoo趣儿
›
Geek
›
程序员
›
面试题:如何 O(n) 的复杂度内筛选 60 亿人的身高 ...
面试题:如何 O(n) 的复杂度内筛选 60 亿人的身高
查看
1120
|
回复
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 页
下一页
返回列表
您需要登录后才可以回帖
登录
|
立即注册
发表回复
浏览过的版块
分享发现
二手交易
Windows
HarmonyOS
优惠信息
IOS/macOS
工作求职
QQ 微信
服务器
通讯人
搜索
热门主题
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
返回顶部