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

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) 了

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

热门主题

时隔 N 个月回顾之前说想要做空泡泡玛特

关于 ventoy+win11+USB3.0 的卡死问题请教

[开源]Claude Code 支持的供应商太少，所以

giffgaff实体卡停发中国了

南非有没有代收款的

快手纵容双相情感障碍患者低俗直播，如何举

MiniMax-M2 在 CC 中试用了下用来写 dart

[iOS 去开屏广告] LOON 喂饭级说明书

今天被网信办打电话让删除文章了

90后真的老了，有几根白头发了

热门板块

公告

网站帮助 - Yoo趣儿

我们的愿景

在 Yoo趣儿投放广告

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