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

Daredevil0086

OP

2023-5-30 15:21:29

@edward1987 #8
@raycool #13 这是 O(nlogk) 吧

UnknoownUser 2023-5-30 15:22:07

兄弟们，面试官好像想考察的是怎么用身高做文章，我最终交上去的答案是 7 楼贴的 leetcode 题目的快排版本答案；
感觉这题，好像跟算法没关系~~~~属于动脑子的那种

UnknoownUser 2023-5-30 15:22:55

// (3-1.9)/0.05=22
int counter[22];

xuanbg 2023-5-30 15:23:38

@UnknoownUser 时间复杂度为 O(n)就只能每个数据都访问一次咯，大致猜测一下前 1000 高的人类应该在 1.9-3.0m 之间，所以遍历一次用计数器把它们都记录下来

FACEB00K 2023-5-30 15:24:38

6 楼正解

tuxz 2023-5-30 15:25:10

@codingbody
@picone k 不是一个常数吗，这里是 1000

icyalala 2023-5-30 15:25:58

线性直方图

picone 2023-5-30 15:26:37

"前 1000 高的数据" 要去重吗?

lymanlai 2023-5-30 15:27:27

@FACEB00K #24 其实是 n 次大小为 1000 的堆插入，应该是 n * log2(1000)

mxT52CRuqR6o5 2023-5-30 15:27:57

感觉在写回字的几种写法。。

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

浏览过的版块

热门主题

福建一中学强制女生剪“斜面短发”

小伙回应捡2267.83克巨型金条

男子坐飞机想起没关火机长出手了

男子想起燃气灶未关求助机长联系物业

“嘎子哥”谢孟伟被行政拘留7天

波音空难唯一幸存者近况曝光

"嘎子哥"穿警服直播被行拘7天

柯克枪击案枪手受审作案动机曝光

“隐形战机不隐形啊都看到了”

职工医保账户余额可以转账了

热门板块

公告

网站帮助 - Yoo趣儿

我们的愿景

在 Yoo趣儿投放广告

Yoo趣儿网站用户应遵守规则