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

热门主题

被网警打电话关站关站网站有评论都不

好便宜，没忍住，买了十年。

各位站长们根据你们的测算这个网站一年可

有没有39健康网或者其他平台的内部号

请教各位高手我这个竞争对手天天来投诉我

老站长每次钓鱼都是坑冠

马云、马化腾懂代码吗？

自建的ai中转站，搞付费行吗

为什么我们站长是这个抠门群体？

有几个24年的个备域名出售，有要的老板么

热门板块

公告

网站帮助 - Yoo趣儿

我们的愿景

在 Yoo趣儿投放广告

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