这是一个创建于 3151 天前的主题，其中的信息可能已经有所发展或是发生改变。
具体该如何实现，我完全没头绪 只能想先排序然后找
 | 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 graycreate 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