百度的一个面试题：从 1 亿个无序数据里找第 5000W 个

[a1310747]

具体该如何实现，我完全没头绪 只能想先排序然后找

[roychan]

Median of medians … O(n)

[neosfung]

@danielmiao 不好意思，以为你是题主，我搞错了，回复的是题主的问题，不是你的问题。

[neosfung]

@danielmiao 关于你这个问题，是肯定存在的。所以这个文章后面就提到了解决方法 “因此不能将数据随便均分到不同机子上，而是要根据 hash 后的值将它们映射到不同的机子上处理，让不同的机器处理一个数值范围。”

[ic2y]

1 亿数字是 4GB 内存，可以直接加载进内存

对 快速排序做点改动，就能实现。

快排第一趟分治结束的时候，会以一个数字为轴，左边小于这个数字，右边大于这个数字，而且这个轴的下标是知道的。

如果下标等于 5000w ，那就直接买命中，如果下标小于 5000w ，对右半部进行快排的第二趟快排。如果大于 5000w ，对左半部进行快排的第二趟。

以此类推，得出 5000w 的是几。

[danielmiao]

@neosfung 感觉自己突然傻 B 了。。。。

[mystzain]

先对前面 N 条数据采样，分析一下分部规律，然后决定一个策略，分成多个区间，然后从原始数据那边取值分拣到多个区间里面，统计各个区间内的条目数。决定对哪个区间进行进一步的分拣或者排序。这样行吗……？

[eyp82]

建议别这么急着就解题, 要先问一下详细情况, 暂时想到一些:
1. 数据类型
2. 每条数据的长度范围, 长度分布情况(最好给个 histogram)
3. 全部数据的排序情况, 是基本有序, 还是乱序
4. 对性能 /延迟和资源占用的要求(性能高延迟低的, 资源占用可能会很大, 合理取舍)
5. 内存大小(是否能全部加载到内存)
6. 解决这个问题的时间要求.(要求在多长时间内搞定之类)
7. 可能还要考虑这个算法的可靠性要求(比如要求可靠性几个 9)

根据具体的情况, 才能选择合适的算法.

这只是问题本身, 如果考虑的更全面一点, 在问上述的问题前后, 还要问的是具体的也无需求, 是否真的需要这个场景, 还是可以用逻辑上等价的其他成本更小的操作代替?

[mcfog]

当年面试唯一答不出来的就是类似的排序算法变形题，面试官都想往我脸上甩堆排序三个大字了，我愣是想不起来只能疯狂聊如何优化快排…

不管怎么说，只能想到先排完序的话，算法没学好（或者说学成背公式了）

[ghui]

m

[vanquish70]

二分法

[ljcarsenal]

mark

[wohenyingyu02]

既然是无序数组，直接随便取一个在 iterator 中把它定义成第 5000w 个不就行了吗？谁规定必须要从第一个开始遍历？