具体该如何实现,我完全没头绪 只能想先排序然后找
1
msg7086 2017-02-28 16:45:50 +08:00
a[5000w]?
你是想说排大小排第 5000w 的那个? |
2
xxdd 2017-02-28 16:50:53 +08:00
select t.numbe from table t order by t.number limit 50000000,50000000
简单 粗暴!速度慢 加内存 加索引 |
3
msg7086 2017-02-28 16:54:02 +08:00
要我做的话,小顶堆或者半个快排。
|
4
exoticknight 2017-02-28 17:00:24 +08:00
感觉像编程珠玑里面的一题?
|
5
neosfung 2017-02-28 17:06:53 +08:00
|
6
morefreeze 2017-02-28 17:07:30 +08:00 3
就是快排分组那个算法改一下,每次只用去其中一半找就行了,记得复杂度平均下来是 N
|
7
Valyrian 2017-02-28 17:09:49 +08:00
无序数组找中位数是经典面试题啊= =
https://en.wikipedia.org/wiki/Median_of_medians |
8
srlp 2017-02-28 17:14:23 +08:00 via iPhone
这是算法题吧,可以考虑快排或者最小堆。
|
9
2lecl 2017-02-28 17:16:20 +08:00
可以反问一下面试官,数的分布情况
如果分布均匀,就 mapreduce |
10
a1310747 OP 最近面试被打击的不行...
|
11
ninjadq 2017-02-28 17:40:22 +08:00 1
先用 O(n)的 shuffle 算法打散,然后用快排的 partition 操作一步步逼近
|
12
kindjeff 2017-02-28 17:41:39 +08:00
是什么数据?如果是数值类型的话,我有一个思路不知道行不行。
把 1 亿个数遍历一遍,找到数值的范围(最大值和最小值),比如是 0 到 100 亿。 然后把它分成 10 万个区间,第一个区间代表数值是在 0 到 10 万,第二个区间是 10 万零 1 到 20 万以此类推。然后像桶排序那样,把这 1 亿个数遍历一遍并放入数值所在的区间。然后就可以知道每个区间的数值个数,然后直接可以定位到一个区间。 然后以此类推。 |
13
binux 2017-02-28 17:46:54 +08:00
百度拿这个问题问了 10 年了吧
|
14
lishunan246 2017-02-28 18:33:34 +08:00
quick select
|
15
danielmiao 2017-02-28 19:35:04 +08:00
@neosfung 这个文章我看了,关于分治法的一个疑问,一个大文件取出现概率前 100 的数,就是吧一个大文件分成 N 份以后取每个文件的前 100 ,再归并排序,但是为什么整个文件的前 100 的数一定在这 N 份文件的 TOP100 里面??会不会出现一个数是每个文件的 TOP101 ,但是整个文件里面是 TOP100 内的?
|
18
snnn 2017-02-28 20:54:24 +08:00 via Android
方法有很多种,我告诉你一个一般人不知道的:区间估计。先采样,然后做区间估计。然后拿这个区间去筛原始的 input 。然后随便怎么搞都行。
|
19
billlee 2017-02-28 21:07:21 +08:00
半边的快排,复杂度 O(n), 这不是基础算法吗?
|
20
neosfung 2017-02-28 22:43:31 +08:00
@danielmiao 你可能理解错我的分治法的意思了
假设是 INT32 的类型,你就建个大小为 2^32 的 array 遍历原始数据,每个数在 array 相对应的位置加一 然后遍历 array ,就知道 5000W 是哪个数了 内存不能够建 2^32 大小的数组?没关系,你可以建个 2^16 大小的数组,每个元素是个指针,指向一个 2^16 大小的数组。然后每个数据可以切分为前后两部分。 百度问你这条题,是因为还有 follow up 的问题的 就是如果这些数据都不能一次放到内存里面呢?如果这些数据都分散在很多台机器上呢。 都可以用我提到的方法通过外存来解决 |
21
roychan 2017-02-28 22:46:57 +08:00
Median of medians … O(n)
|
22
neosfung 2017-02-28 22:50:23 +08:00
@danielmiao 不好意思,以为你是题主,我搞错了,回复的是题主的问题,不是你的问题。
|
23
neosfung 2017-02-28 22:54:31 +08:00 1
@danielmiao 关于你这个问题,是肯定存在的。所以这个文章后面就提到了解决方法 “因此不能将数据随便均分到不同机子上,而是要根据 hash 后的值将它们映射到不同的机子上处理,让不同的机器处理一个数值范围。”
|
24
ic2y 2017-02-28 22:55:28 +08:00 1
1 亿数字是 4GB 内存,可以直接加载进内存
对 快速排序做点改动,就能实现。 快排第一趟分治结束的时候,会以一个数字为轴,左边小于这个数字,右边大于这个数字,而且这个轴的下标是知道的。 如果下标等于 5000w ,那就直接买命中,如果下标小于 5000w ,对右半部进行快排的第二趟快排。如果大于 5000w ,对左半部进行快排的第二趟。 以此类推,得出 5000w 的是几。 |
25
danielmiao 2017-02-28 23:16:41 +08:00
@neosfung 感觉自己突然傻 B 了。。。。
|
26
mystzain 2017-03-01 01:25:09 +08:00
先对前面 N 条数据采样,分析一下分部规律,然后决定一个策略,分成多个区间,然后从原始数据那边取值分拣到多个区间里面,统计各个区间内的条目数。决定对哪个区间进行进一步的分拣或者排序。这样行吗……?
|
27
eyp82 2017-03-01 03:59:03 +08:00 1
建议别这么急着就解题, 要先问一下详细情况, 暂时想到一些:
1. 数据类型 2. 每条数据的长度范围, 长度分布情况(最好给个 histogram) 3. 全部数据的排序情况, 是基本有序, 还是乱序 4. 对性能 /延迟和资源占用的要求(性能高延迟低的, 资源占用可能会很大, 合理取舍) 5. 内存大小(是否能全部加载到内存) 6. 解决这个问题的时间要求.(要求在多长时间内搞定之类) 7. 可能还要考虑这个算法的可靠性要求(比如要求可靠性几个 9) 根据具体的情况, 才能选择合适的算法. 这只是问题本身, 如果考虑的更全面一点, 在问上述的问题前后, 还要问的是具体的也无需求, 是否真的需要这个场景, 还是可以用逻辑上等价的其他成本更小的操作代替? |
28
mcfog 2017-03-01 08:15:15 +08:00 via Android
当年面试唯一答不出来的就是类似的排序算法变形题,面试官都想往我脸上甩堆排序三个大字了,我愣是想不起来只能疯狂聊如何优化快排…
不管怎么说,只能想到先排完序的话,算法没学好(或者说学成背公式了) |
29
ghui 2017-03-01 08:20:57 +08:00 via iPhone
m
|
30
vanquish70 2017-03-01 08:35:38 +08:00
二分法
|
31
ljcarsenal 2017-03-01 11:44:50 +08:00 via Android
mark
|
32
wohenyingyu02 2017-03-01 22:30:45 +08:00
既然是无序数组,直接随便取一个在 iterator 中把它定义成第 5000w 个不就行了吗?谁规定必须要从第一个开始遍历?
|