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

[a1310747]

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

[msg7086]

a[5000w]？

你是想说排大小排第 5000w 的那个？

[xxdd]

select t.numbe from table t order by t.number limit 50000000,50000000

简单 粗暴！速度慢 加内存 加索引

[msg7086]

要我做的话，小顶堆或者半个快排。

[exoticknight]

感觉像编程珠玑里面的一题？

[neosfung]

分治
http://blog.csdn.net/v_july_v/article/details/6279498

[morefreeze]

就是快排分组那个算法改一下，每次只用去其中一半找就行了，记得复杂度平均下来是 N

[Valyrian]

无序数组找中位数是经典面试题啊= =
https://en.wikipedia.org/wiki/Median_of_medians

[srlp]

这是算法题吧，可以考虑快排或者最小堆。

[2lecl]

可以反问一下面试官，数的分布情况
如果分布均匀，就 mapreduce

[a1310747]

最近面试被打击的不行...

[ninjadq]

先用 O(n)的 shuffle 算法打散，然后用快排的 partition 操作一步步逼近

[kindjeff]

是什么数据？如果是数值类型的话，我有一个思路不知道行不行。

把 1 亿个数遍历一遍，找到数值的范围（最大值和最小值），比如是 0 到 100 亿。
然后把它分成 10 万个区间，第一个区间代表数值是在 0 到 10 万，第二个区间是 10 万零 1 到 20 万以此类推。然后像桶排序那样，把这 1 亿个数遍历一遍并放入数值所在的区间。然后就可以知道每个区间的数值个数，然后直接可以定位到一个区间。

然后以此类推。

[binux]

百度拿这个问题问了 10 年了吧

[lishunan246]

quick select

[danielmiao]

@neosfung 这个文章我看了，关于分治法的一个疑问，一个大文件取出现概率前 100 的数，就是吧一个大文件分成 N 份以后取每个文件的前 100 ，再归并排序，但是为什么整个文件的前 100 的数一定在这 N 份文件的 TOP100 里面？？会不会出现一个数是每个文件的 TOP101 ，但是整个文件里面是 TOP100 内的？

[h3nng]

@binux 233 ，我当年面试也是这个问题。。

[a1310747]

@h3nng 你是怎么回答的呢

[snnn]

方法有很多种，我告诉你一个一般人不知道的：区间估计。先采样，然后做区间估计。然后拿这个区间去筛原始的 input 。然后随便怎么搞都行。

[billlee]

半边的快排，复杂度 O(n), 这不是基础算法吗？

[neosfung]

@danielmiao 你可能理解错我的分治法的意思了
假设是 INT32 的类型，你就建个大小为 2^32 的 array
遍历原始数据，每个数在 array 相对应的位置加一
然后遍历 array ，就知道 5000W 是哪个数了
内存不能够建 2^32 大小的数组？没关系，你可以建个 2^16 大小的数组，每个元素是个指针，指向一个 2^16 大小的数组。然后每个数据可以切分为前后两部分。
百度问你这条题，是因为还有 follow up 的问题的
就是如果这些数据都不能一次放到内存里面呢？如果这些数据都分散在很多台机器上呢。
都可以用我提到的方法通过外存来解决