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

浏览过的版块

热门主题

国产英伟达，摩尔把上市融资的75亿元拿去买

✅DMIT 三网 GIA CMIN2 MALIBU EB 维多利亚

有MJJ遇到过TG号全部设备都被登出了吗？

【快讯】HostHatch Seoul HH 新节点首尔

Hk-One-0.5G-52-LS 少量放貨速度

公司项目分享：硅谷人工智能公司 Nexa AI

拿到了 300 来部短剧的海外发行版权，下一

长话短说大家觉得花三十万结婚，存款花完

建议拉黑 IObit 旗下所有软件

重度苹果用户投华做了两面派

热门板块

公告

网站帮助 - Yoo趣儿

我们的愿景

在 Yoo趣儿投放广告

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