这是一个创建于 2823 天前的主题，其中的信息可能已经有所发展或是发生改变。
具体该如何实现，我完全没头绪 只能想先排序然后找
 |
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 个不就行了吗？谁规定必须要从第一个开始遍历？
|
Select Language