这是一个创建于 542 天前的主题，其中的信息可能已经有所发展或是发生改变。
完整的题目差不多是这样的：
现在有一个文件 a.txt ，其中放的内容就是 60 亿人的身高，每个身高数据都保证是以.0 或者.5 结尾的（比如说 180.0 ，175.5 ）；现在请筛选出其中前 1000 高的数据；
要求时间复杂度是 o(n);
面试官说这玩意不是一个单纯的算法，身高数据可以做点文章……但到最后还是没想出来………………有没有高智商 V 友可以解答一下
第 1 条附言 · 2023-05-29 19:42:16 +08:00
感谢各位高智商 V 友的各种回答和意见，感觉基本确定了答案就是 1L 和 6L 的方案就是面试官想要的~~~
总之，千言万语汇成一句话：
家人们，爱你啾咪❤，mua~~
总之，千言万语汇成一句话：
家人们，爱你啾咪❤，mua~~
 |
1
fengjianxinghun 2023-05-29 16:15:05 +08:00  5
人类的身高是有上下限的，正确点说就是 0.5-3 米之间，而且他保证了是.0/.5 结尾，就减少到一个更小的数值集合，这样想你是不是就懂了?
|
 |
2
lolizeppelin 2023-05-29 16:15:50 +08:00 1
遍历的时候超过 2 米的.....或者低一点 1.95
|
 |
3
iamzuoxinyu 2023-05-29 16:16:10 +08:00
桶排序
|
 |
4
Nugine0 2023-05-29 16:20:20 +08:00 via Android 3
基数排序
|
 |
5
Daredevil0086 OP @iamzuoxinyu 桶排序最差能到 O(n^2)吧，不在 O(n)内
|
 |
6
leogm9408leo 2023-05-29 16:21:54 +08:00 66
数据是以.0 或者.5 结尾，意味着这是个有范围的离散数据而不是连续数据。假设人类的身高区间是 10 厘米-250 厘米，间距 0.5 厘米，其实也就（ 250-10 ）*2=480 个。作 480 个数据桶，遍历一遍就可以把 60 亿数据都放到这 480 个数据桶里，然后取不为空的最大身高值的桶里的数据即可
|
 |
7
devfeng 2023-05-29 16:22:24 +08:00
https://leetcode.cn/problems/kth-largest-element-in-an-array/ 第 k 个最大元素，思路是一样的
|
 |
8
edward1987 2023-05-29 16:22:36 +08:00 4
前 1000 高的，又不是所有都排序，用一个数组存当前最高的 1000 个，遍历一遍，遇到更高的就替换数组内容就好了啊。复杂度就是 0(n)
|
|
9
Daredevil0086 OP @fengjianxinghun 额，即使是不看结尾小数，好像稳定在 O(n)内的排序算法也没有吧
|
 |
10
githmb 2023-05-29 16:22:58 +08:00
一个容量为 1000 的向量，60 亿数据依次往里面塞，每塞一次做个排序
|
|
11
Daredevil0086 OP @devfeng 哦哦哦哦，那我算答对了？我用的是快排那个…………………………但是还是没太理解怎么用身高这点来做优化
|
 |
12
insanny 2023-05-29 16:25:01 +08:00
同意 6 楼的思路
|
 |
13
raycool 2023-05-29 16:25:06 +08:00
堆排序
|
 |
14
sun1991 2023-05-29 16:25:08 +08:00
开一个 HashMap, 把可能的身高数据以 key 的形式预先插入. 然后遍历集合, 插入 HashMap. 最后以身高为 key, 从高到底, 从 HashMap 拿数据, 凑满 1000 即可.
|
 |
15
FACEB00K 2023-05-29 16:25:27 +08:00
不考虑身高数据，构建 size 为 1000 的最小堆；
如果考虑升高数据，用一个数组统计身高就能解决吧，数组下标和身高有映射关系，而且身高范围是固定的；最后逆序遍历数组 |
|
16
Daredevil0086 OP @edward1987 那是平均复杂度吧，面试官这么说的……
|
 |
17
coyoteer 2023-05-29 16:26:58 +08:00
计数排序？
|
 |
19
codingbody 2023-05-29 16:31:34 +08:00
|
|
20
Daredevil0086 OP 兄弟们，面试官好像想考察的是怎么用身高做文章，我最终交上去的答案是 7 楼贴的 leetcode 题目的快排版本答案；
感觉这题，好像跟算法没关系~~~~属于动脑子的那种 |
 |
21
UnknoownUser 2023-05-29 16:32:39 +08:00
// (3-1.9)/0.05=22
int counter[22]; |
|
22
UnknoownUser 2023-05-29 16:35:30 +08:00
@UnknoownUser 时间复杂度为 O(n)就只能每个数据都访问一次咯，大致猜测一下前 1000 高的人类应该在 1.9-3.0m 之间，所以遍历一次用计数器把它们都记录下来
|
 |
23
xuanbg 2023-05-29 16:38:08 +08:00
6 楼正解
|
|
24
FACEB00K 2023-05-29 16:38:26 +08:00
|
 |
25
tuxz 2023-05-29 16:40:04 +08:00
线性直方图
|
 |
26
icyalala 2023-05-29 16:45:11 +08:00
"前 1000 高的数据" 要去重吗?
|
 |
28
lymanlai 2023-05-29 16:48:31 +08:00
感觉在写回字的几种写法。。
|
 |
29
mxT52CRuqR6o5 2023-05-29 16:49:04 +08:00
我很怀疑面试官是不是自以为是的认为桶排序算是一种优化
|
 |
30
IwfWcf 2023-05-29 16:52:33 +08:00
面试官都提示得那么明显了，就是在提示桶的数量很少啊……
|
|
31
FACEB00K 2023-05-29 16:57:39 +08:00
@picone 一般是像你这么算的，每次都是和堆顶比较，比堆顶大的才删除堆顶，再插入；如果比堆顶小，直接就 pass 了，算法复杂度就是 O(nlogk)；但是身高应该是符合正态分布的，前 1000 名身高可能只占百分之零点零几，甚至更少，60 亿数据中，基本上没多少次插入
|
 |
32
tyler1128 2023-05-29 17:00:09 +08:00 1
受 6 楼启发，480 个桶，先取 1000 个放入各自的桶内，然后淘汰掉数量不为 0 的最小的桶后面的所有桶，初始化一个计数器，初始值为最小的桶内令牌的数量。后面再次取数时，如果小于最小的桶，直接丢弃（节省哈希时间），如果这个数是此时场上最小的桶，则计数器加 1 ，如果不是最小的桶，计数器-1 ，当计数器为 0 时，丢弃最小的桶，重新排序找到新的最小的桶，计数器设置为新的最小的桶内令牌数量。重复该操作，直到遍历完 60 亿数，此时剩下的就是最大的 1000 个（数量可能会超过 1000 ，因为最小的桶可能有很多相同的值）。
|
 |
33
picone 2023-05-29 17:00:14 +08:00
@FACEB00K #31 题目没有这个假设，这样不太合适。 即使有这个假设，按照二八分布，顶多也只能是 0.8n + 0.2 * n * log2(1000)，也不完全是 O(n)
|
 |
34
HashV2 2023-05-29 17:00:36 +08:00
嗯 应该就是先考察一个 topk 的算法问题，然后主要让你谈这个数据可以干嘛
60 亿是一个全球人数级别的数据，但是我也想不出这个数据到底可以做啥文章😂 |
 |
35
UIXX 2023-05-29 17:01:50 +08:00
也不考虑 O(n)，我们的期望是 [一轮遍历+尽可能少的空间] 达到筛选目的。
在现实中处理此类问题需要数据清洗并建模，简单地，我们需要预估身高分布，比如是全随机分布还是正态分布？ 无论是哪一种，我们都能估算出一个合适的身高范围，如果用桶，这个范围会使桶的数量大大减少。 |
 |
36
wanguorui123 2023-05-29 17:08:56 +08:00
分别创建：List ，最大变量 A ，最小变量 B ，遍历 txt 数据时每次和最大变量 A 和最小变量 B 对比，将最大数据计入即可，然后加入 List ，让 List 始终保持 1000 个以内即可，遍历完成后对 List 快速排序既可以，非常简答
|
 |
37
akira 2023-05-29 17:15:34 +08:00
这样 身高数据 是有限的啊。。统计出 每个高度的人数，然后从上往下拿够 1000 个
|
 |
38
pkoukk 2023-05-29 17:16:20 +08:00
@wanguorui123
不行的。假如数据集中的第一个值是 max,第二个值是 min ，那 list 跑到最后只有两个元素。 |
 |
39
e7 2023-05-29 17:33:50 +08:00
1L 就已经给出标准答案了，任何带比较的都超过 O(n)了，btw：面试官挺无聊的
|
 |
40
mmuggle 2023-05-29 17:59:07 +08:00
2000cm 不够高是吧？直接 O(1) 🤣
|
 |
41
darkengine 2023-05-29 18:03:29 +08:00
确实是基数排序，只不过基用的是人类的身高，例如 355.0, 354.5 。
|
 |
42
8355 2023-05-29 18:24:44 +08:00
1 楼说的是对的,这是常识问题加基本方案解决.
其他说 60 亿次遍历或者比较的方案最大的问题就是存储 60 亿的问题必然是不符合出题者的意图的. 我猜应该就是要问布隆过滤器吧. |
 |
43
cclin 2023-05-29 18:59:39 +08:00
打开算法导论，翻到 112 页，得到一个最差时间复杂度 O(n) 的算法
顺便 60 亿个数字在现在的硬件上不算一个很大的规模 鉴定为题出得不行 |
 |
44
iOCZ 2023-05-29 19:06:30 +08:00
topK 算法挺常见的。用优先级队列构造 1000 个容量的小根堆，比堆顶小的舍弃，比堆顶大的进入。这个复杂度是 O(n*log2n)。要达到 o(n)的话，得使用空间复杂度更高的，类似计数排序。因为身高肯定是一个有限的数据点集，可以简单通过计数来实现获取前 1000 的数据。
|
 |
45
yzbythesea 2023-05-29 19:11:16 +08:00 via iPhone
经典堆排序问题
时间复杂度说 O(nlogk) 是错误的、说明不理解复杂度一说。n 和 k 不在一个量级可把 logk 视为常量。 |
 |
46
XiLingHost 2023-05-29 19:30:40 +08:00
这不是很典型的计数排序场景吗......
|
 |
47
NoOneNoBody 2023-05-29 19:58:22 +08:00
身高符合正态分布，六百万分之一只考虑>2m 就够了
算法我是文盲，pass |
 |
48
ytmsdy 2023-05-29 19:59:08 +08:00
o(n)的复杂度应该不难吧。只需要前 1000 ，又不用全部数据排序。
搞一个长度为 1000 的数组，搞一个插入排序，如果值大于 1000 中的最小值，那就插入，并把最后那个元素给删掉。 其实也就是 1000*o(n)的复杂度，也就 O(n)的复杂度 |
|
49
iOCZ 2023-05-29 20:03:57 +08:00
@yzbythesea 你说得对，我这个复杂度写错了。
|
 |
50
geelaw 2023-05-29 20:07:41 +08:00 via iPhone 5
O(n) 和 o(n) 是不同的意思，后者是前者的真子集。更不能写成 0(n)，最后这个东西只能被理解为零乘 n ，也就是 0 。
另外问题的表述不清楚：n 是什么？ 合理的表述如下：文件里有 n 个人的身高（厘米）且每个数据都是 整数.0 或者 整数.5 ，求最高的 1000 个人的身高。要求算法是 O(n) 时间的。 60 亿和 1000 都是常数，原来表述下的问题可以在 O(1) 时间内解决。 |
 |
51
ershierdu 2023-05-29 20:22:13 +08:00
@geelaw
想起了去年找实习的面试，一道字符串相关的题，大意是给定一个字符串，找出其中第一个“只出现了一次的字符”的下标。我用 HashMap 做的，在已经明确字符串只包含英文字母的前提下，面试官非说最坏时间复杂度是 O(nlog n)，因为底层的红黑树最坏就是 O(n logn)… |
 |
53
wudicgi 2023-05-29 20:45:38 +08:00
用 hashtable, key 为身高, value 为该身高出现的次数
最后取出 hashtable 的 key, 按从大到小的顺序排序，再逐个看 value, 输出 key 的值直到 value 加起来 >= 1000 这样可行不？ |
 |
54
sylxjtu 2023-05-29 20:51:54 +08:00
可以参考《编程珠玑》第一章，讲得非常清楚
|
 |
55
tiandao84 2023-05-29 21:03:10 +08:00 via iPhone
好久没做题我也知道😯遍历一遍构建大顶堆，复杂度 O(n+LogN)
|
 |
57
20015jjw 2023-05-29 22:34:55 +08:00 via iPhone
bucket sort 例题啊 cs61b…
|
 |
58
veike 2023-05-29 22:43:16 +08:00
@leogm9408leo 兄弟有博客吗，关注一波
|
 |
60
NXzCH8fP20468ML5 2023-05-29 23:56:01 +08:00
首先，1k 的排序可以视作常数，剩下的看你们发挥了。
|
 |
61
Badlink 2023-05-30 00:38:53 +08:00
60 亿，假设每个身高浮点数表示的话是 8 字节，大概 5 * 10^10 B = 50G 。如果内存放不下的话就放 50 个文件，每次对一个文件桶排序，取前 1000 个，最后对这 50 个文件共 50000 个数再桶排序一次
|
 |
62
oamu 2023-05-30 06:25:16 +08:00 via iPhone
@picone 时间复杂度是对于输入来说的，在这个问题里，输入是 60 亿的身高数据，用一个大小为 1000 的堆进行排序取前 1000 大的数据，这个 1000 就是个常数，总的时间复杂度就是 O(n)。
|
 |
63
tyrantZhao 2023-05-30 06:54:25 +08:00
位图
|
 |
64
k9982874 2023-05-30 08:09:01 +08:00 via Android
这题内存没限制的情况下不是 for loop 一遍就出结果了吗
|
 |
65
mingl0280 2023-05-30 08:28:49 +08:00 via Android
先来一个长度 480 的 int 数组，然后身高*2%480 到桶里，最后从前往后输出不为零的项就完事了
|
|
66
mingl0280 2023-05-30 08:29:21 +08:00 via Android
如果要剪枝还可以直接滤掉身高小于两米的……
|
 |
67
hxysnail 2023-05-30 08:33:25 +08:00
用一个规模为 1000 的最小堆，然后遍历数据，如果比堆顶大，就替换堆顶，再调整一下堆结构。遍历完好，堆里面的数据就是前 1000 。
由于 1000 是固定的，每次维护最小堆的时间可以认为是一个常量 k ，这样一来，时间复杂度为 O(kN)，等价与 O(N)。 这个方法适用于任何数据，从 N 个数据中取最大或最小的 n 个，只要 n 远小于 N 就行。 |
 |
68
bianhui 2023-05-30 08:48:30 +08:00
60 亿人任何一个人的身高都不止一个人，只需找到最高的人，然后输出一千次就行了
|
 |
69
WngShhng 2023-05-30 09:03:18 +08:00
不是吧，如果要在更小的范围内搜索，前提是数据是有序的，如果数据经过排序，复杂度就达不到 O(n) 的要求。不考虑内存的话，遍历一遍，将 top 高的数据记录在一个列表里，同时记录这个列表的最小值，然后如果遇到高于这个最小值的或者列表还没满，这个时候把数据塞到列表里，同时更新列表的最小值，即可。这样对于列表不需要进行额外的排序浪费时间复杂度，这样才可以达到 O(n) 的要求。如果考虑实际情况，这个问题难度在于如何分块读取数据，以保证读取数据到内存之后，内存不会爆掉，所以，.0 或者 0.5 可能是分块读取的依据（当然你应该问一下数据在文本中是如何存储的
|
 |
70
magicyao 2023-05-30 09:19:38 +08:00
很明显的桶排，然后取 1000 个，1000 是常数可以不计入复杂度中
|
 |
71
summerLast 2023-05-30 09:20:25 +08:00
可以用桶 比如 200cm 对应第 4000 个桶 然后每个桶里这个身高对应的人数，找到满足条件的最大的几个桶的身高
下一步就是如何用并发等提高入桶的统计速度，如先 xx 线程处理入桶，然后 xx 线程合并桶 几次迭代之后就有了上述的统计 |
 |
72
loryyang 2023-05-30 09:43:07 +08:00
这种都老题了，其实没啥意思。知道解法会觉得很简单，不知道的，咋可能在面试的时候想出来。所以我面试从不出这种题目，不公平，没有筛选意义
|
 |
73
limitsy 2023-05-30 10:07:01 +08:00
1 楼的意思应该也是哈希表吧？把身高上下限定为 0-3 米 转换为毫米 0-3000 ，然后可以建立一个长度为 3000 的整型数组（其实如果小数都是.0/.5 ，都不需要这么大的数组）。那么遍历身高，只需要把 arr[身高 * 10] ++ 。最后再从数组最大开始反向遍历取出前 1000 就可以了。
|
 |
75
leeraya 2023-05-30 10:43:03 +08:00
典型的 topk 问题
|
 |
76
enson110 2023-05-30 10:51:42 +08:00 1
贴一个 GPT4 给的答案，是的真的强：
``` 如果你需要一个 O(n) 时间复杂度的解决方案，那么可以使用一个叫 "桶排序" 的技术。"桶排序" 是一种可以在线性时间内完成的排序算法，但是这需要对输入数据有一些特定的假设。 根据你的问题描述，人的身高是以 0.5 的单位进行记录的。我们可以假设一个可能的范围，比如说从 0.0 到 300.0 。然后我们创建 600 个桶（一个桶代表 0.5 的身高），每个桶都对应了一个可能的身高。然后遍历所有的数据，根据身高将人放到对应的桶里。这一步的时间复杂度为 O(n)。 接下来，我们可以从最高的桶开始，检查每个桶里有多少人。然后从这个桶开始向下找，直到找到 1000 个人。这一步的时间复杂度为 O(1)，因为桶的数量是固定的。 这样，整个算法的时间复杂度为 O(n)。需要注意的是，这种算法的效率取决于我们的假设是否准确，以及数据是否均匀分布。如果数据的分布很不均匀，桶排序的效率就会降低。 这是一个基本的桶排序应用。如果需要处理更复杂的情况，比如说数据的范围不确定，或者桶的数量太多等，我们可能需要使用其他的技巧，比如说动态地创建桶等。但是基于你的问题描述，这个基本的方法应该就可以工作得很好。 ``` |
 |
77
fdd92 2023-05-30 11:13:20 +08:00
@picone 时间复杂度讨论的是总时间随项的增加而增加的情况，所以堆大小是常数就不影响时间复杂度。如果堆大小不是常数，那时间复杂度就是 O(n log m)。
|
|
78
oamu 2023-05-30 12:21:33 +08:00
@picone #74 要比较前 1000 和前 1000000 ， 实际上是把 1000 当作输入，那它也就不是常数了，用堆排序时间复杂度是最坏就是 O(n logk)；但按照原题的条件和常识，可以知道可能的身高数量是有限的，且与数据规模（输入）无关，可以看成一个常数，每个身高最多插入堆 k 次，那么用堆排序最坏的时间复杂度应该是 O(n + k log k)。之前默认将 1000 看作常数是考虑不周。
|
 |
79
jameskongawork 2023-05-30 13:10:12 +08:00
o(1) 人均 180
|
 |
80
buxudashi 2023-05-30 14:14:23 +08:00
这个，结果集其实是个链表。一个一个插入得了。
[身高 2 米 4] =N 个人 [身高 2 米 35] =M 个人 |
 |
81
wengyanbin 2023-05-30 15:32:27 +08:00
人类的身高应该也是满足正态分布的，前 1000 占据 60 亿的比例，大体可以划出一个区间范围，作为过滤条件可以大幅度过滤掉不符合的
|
 |
82
jixiangqd 2023-05-30 15:37:42 +08:00
这感觉像是脑筋急转弯。。。不过问题也许也是有些许应用价值的，可以作为种思路学习下
|
 |
83
iX8NEGGn 2023-05-30 18:27:00 +08:00 via iPhone
类似词频统计，四层 trie 就能解决 ，第一层 0~3 （人的身高不会超过 3 米），第二层 0~9 ，第三层 0~9 ，第四层只有 0 和 5 ，每个 trie 节点有一个 count ，遍历一边 60 亿人的身高，每种身高有多少人就全得到了
|
 |
84
wangritian 2023-05-30 18:37:27 +08:00
6L 并不是正解，8L 才是
|
 |
85
zengmingyang96 2023-05-30 18:46:20 +08:00
bitmap
|
 |
86
wwbfred 2023-05-30 18:48:41 +08:00
如果题目说身高都是整数，那么很容易就会想到统计每个身高对应的人数。出现半整数不改变题目本质，但具有迷惑性，让人更难想到最简单的方法。
|
 |
87
mrzhangrb 2023-05-30 19:05:02 +08:00
压根不用排序吧， 用哈希 key 为身高，val 为这个身高出现的次数， 遍历一遍， 从最高身高向下取 1000 个
|
Select Language