面试题：如何 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 亿人的身高

浏览过的版块

热门主题

突然想到，测试驱动开发是不是有一个用处是

Surge 如何指定域名不使用 DNS 缓存

gname竟然不能访问了

兄弟们，SEO现在越来越简单化了

【2025】人在前面推，钱在后面追

老铁都是初几上班

你说话的底气来自你的经济实力

66个域名，批量建站等收录，也都配置了http

高速堵成狗，又开了十几个小时。。

《4414站长论坛：草根站长的生存手册与江湖

热门板块

公告

网站帮助 - Yoo趣儿

我们的愿景

在 Yoo趣儿投放广告

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