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

浏览过的版块

热门主题

谁有win10激活码？

全网付费资源10-10更新

Droid送38000000 Token

咸鱼教海外撸美刀赚钱教程是真的吗

确实有的站长一门心思搞技术，不去悟商机、

百度是如何把所有产品做成狗屎的。。。

腾讯云最近有没有什么活动

聊一聊GEO，在AI领域的发展趋势

百科界中的一代神站，应该也是卖了吧

站长们平时都是怎么推广自己网站的？

热门板块

公告

网站帮助 - Yoo趣儿

我们的愿景

在 Yoo趣儿投放广告

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