|
锁定老帖子 主题：一道腾讯面试题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-04-02
10G的文件里都是乱序的整数，要求找出中位数。
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2010-04-02
最后修改：2010-04-02
yangguo 写道 10G的文件里都是乱序的整数，要求找出中位数。
10个数找到中位数的代码怎么写？ 差不多。 |
| 返回顶楼 | |
|
发表时间：2010-04-02
这个.首先你要把这10G的文件读到File流里面就要注意了吧= =.
|
| 返回顶楼 | |
|
发表时间：2010-04-02
等待牛人出现解答
|
| 返回顶楼 | |
|
发表时间：2010-04-02
抛出异常的爱 写道 yangguo 写道 10G的文件里都是乱序的整数，要求找出中位数。
10个数找到中位数的代码怎么写？ 差不多。 用简单办法，解决复杂的问题。高手! |
| 返回顶楼 | |
|
发表时间：2010-04-02
用b树，然后从两端递归称子树重量
|
| 返回顶楼 | |
|
发表时间：2010-04-02
最后修改：2010-04-02
使用MapReduce方式分段并行计算
|
| 返回顶楼 | |
|
发表时间：2010-04-02
从海量数据中找出中位数
http://blog.chinaunix.net/u3/94271/showart_2020121.html |
| 返回顶楼 | |
|
发表时间：2010-04-03
最后修改：2010-04-03
1、取 16*1024 个数，生成一个 TreeMap 。取得最大值 max 和最小值 min。
2、构造一个1024个元素的计数数组 T[i]，对最初的 1024 个数按区间计数； 对 min 和 max 进行 1024 个等分,各等分值为 N[i]。 当数据 N[a]<data<=N[a+1] 时， T[a]++； 3、将大于 N[512-8] 且小于 N[512+8] 的数放入一个新的 TreeMap。 4、开始读取之后的数据，执行2 和 3的操作； 5、根据区间计数，获知中位数处于N[x]区间。 如果正好处于 N[512-8] 且小于 N[512+8]，则可以直接查询数据。 否则，重新读取一次数据，将处于 N[x] 区间的数，放入一个 TreeMap 中，获得中位数。 6、如果某个区间的数据量超过 200万，则对该区间进行分区，分成 1024 个区，并进行计数。 嗯嗯，计数要智能一些，可以分拆、合并计数据区间。最大值最小值要随时取。 |
| 返回顶楼 | |
|
发表时间：2010-04-03
最后修改：2010-04-03
随机找到个数
把数据重排一下 大于这数的放左 小于这数的放右 少的部分变成一个箱的总个数其它不管 多的那边再生成两个箱 每次计算出来中值可能在哪个箱中 就拆哪个箱子 左右摆动直到中间的数组足够小。。。。 这个复杂度是 O(n*lgn) |
| 返回顶楼 | |
