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

热门主题

操作失误导致公司损失，直属领导被罚 1 万

作为一个35级的坛坛劝新人不要暴露自己的服

小语种盗版电影网站，几乎无风险，但是搞不

由于主流 AI 编程助手太贵/额度消耗太快，

请问 iPhone 有红外线（遥控空调等家电）的

[开源实时数字人 OpenTalking] 重磅支持视

2026 年了，有什么显示器推荐的吗？

给科研宝宝的工具： EasyReader 升级到 1.2

怎么合法的获取美团和饿了么的店铺以及餐品

将于 2026年6月30日起，正式关停 VPS、VDS

热门板块

公告

网站帮助 - Yoo趣儿

我们的愿景

在 Yoo趣儿投放广告

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