|
锁定老帖子 主题：一道腾讯面试题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-04-06
@zhaoyifei
例如：a = {1,2,3,4,5,6,99} 按照你的算法，。。。。 java.util.BitSet 可以搞定本题 |
| 返回顶楼 | |
|
发表时间：2010-04-06
编程珠玑里面的第一道题
|
| 返回顶楼 | |
|
发表时间：2010-04-06
最后修改：2010-04-06
zhaoyifei 写道 sjynt131 写道 提烟而过 写道 xinyulou 写道 提烟而过 写道 xinyulou 写道 这个简单,只需要从头读取然后插入另一个文件,维持中间位数即可,几行代码搞定!
这位仁兄，你太牛了，能否把你的几行代码贴出来让大家共同拜读一下。这里是10G，你拷贝一个还算可行，如果是100G或更大呢，你安排怎么处理的?还有你是怎么在另一个文件中去维持中位数是哪个，是否可以给出你的思路? 哈哈,如果这个问题再加一个条件:只有1M的内存怎么办呢? 首先数据的表示方法要变化一下,用向量来表示整数集合,比如集合{1,3,4,5}可以表示为 010111 第一步,初始化所有位为0,n为多少位,如果位太多可以以文件的形式,文件的第几位.... for [0,n) bit[n] = 0; 第二步,读取源文件,把相应的位置1 for each i in input file bit[i] = 1; 第三步,输出 , 都是排好序的 for [0,n) if(bit[i] == 1) write i on output file 如果有重复数据要处理一下,一样存在两外一个文件里,第几位好多少个,输出的时候判断一下即可 貌似应该差不多了 首先数据的表示方法要变化一下,用向量来表示整数集合,比如集合{1,3,4,5}可以表示为 010111 ——这可是让我大开眼界了 请恕我直言：真不知是我孤陋寡闻，还是你不懂装懂，牛头不对马嘴， 不知所云？若有哪位高手能看懂，还烦指教。 我明白他的意思，可能是建立个足够长的BIT数组,每位代表1个数字在文件中是否存在,比如"集合{1,3,4,5}可以表示为 010111 " 这里0不在集合中,1在集合中,2不在集合中,3、4、5在集合中。遍历1遍文件既可得到所有数字的集合，再采用特定算法取到数组中所有1的中间位置（然后循环BIT数组到:数组和除2个1的位置），再通过数组下标得到这个值。 这个思路是挺独特的，效率也很高。呵呵 这个byte[]你知道是多大吗？比那个文件小不了多少 是的，这个思路存在的问题是重复值怎么处理，所以不能在数组中仅存0或1，至少存储的是每个数字对应的个数才对，那么假如这个个数大于127怎么办？如果用这种方式存储的话，就需要定义一个长为2^32的int类型数组才对，，这的确是需要很大的内存才对。 如果看到我上一个回答的话，就会发现这个思路就是其中说过的利用索引的方式，这个方式的问题就是映射的数据结构本身也很大。另外，在我提出的思路中，将定义的1024x1024的数据改为2^32长度，那么这两种思路的效果就会一样了（可能都是运行不下去...） |
| 返回顶楼 | |
|
发表时间：2010-04-06
对哦，如果是32位还好，64位整数就疯了。。。
|
| 返回顶楼 | |
|
发表时间：2010-04-06
最后修改：2010-04-06
蔡华江 写道 zhaoyifei 写道 sjynt131 写道 提烟而过 写道 xinyulou 写道 提烟而过 写道 xinyulou 写道 这个简单,只需要从头读取然后插入另一个文件,维持中间位数即可,几行代码搞定!
这位仁兄，你太牛了，能否把你的几行代码贴出来让大家共同拜读一下。这里是10G，你拷贝一个还算可行，如果是100G或更大呢，你安排怎么处理的?还有你是怎么在另一个文件中去维持中位数是哪个，是否可以给出你的思路? 哈哈,如果这个问题再加一个条件:只有1M的内存怎么办呢? 首先数据的表示方法要变化一下,用向量来表示整数集合,比如集合{1,3,4,5}可以表示为 010111 第一步,初始化所有位为0,n为多少位,如果位太多可以以文件的形式,文件的第几位.... for [0,n) bit[n] = 0; 第二步,读取源文件,把相应的位置1 for each i in input file bit[i] = 1; 第三步,输出 , 都是排好序的 for [0,n) if(bit[i] == 1) write i on output file 如果有重复数据要处理一下,一样存在两外一个文件里,第几位好多少个,输出的时候判断一下即可 貌似应该差不多了 首先数据的表示方法要变化一下,用向量来表示整数集合,比如集合{1,3,4,5}可以表示为 010111 ——这可是让我大开眼界了 请恕我直言：真不知是我孤陋寡闻，还是你不懂装懂，牛头不对马嘴， 不知所云？若有哪位高手能看懂，还烦指教。 我明白他的意思，可能是建立个足够长的BIT数组,每位代表1个数字在文件中是否存在,比如"集合{1,3,4,5}可以表示为 010111 " 这里0不在集合中,1在集合中,2不在集合中,3、4、5在集合中。遍历1遍文件既可得到所有数字的集合，再采用特定算法取到数组中所有1的中间位置（然后循环BIT数组到:数组和除2个1的位置），再通过数组下标得到这个值。 这个思路是挺独特的，效率也很高。呵呵 这个byte[]你知道是多大吗？比那个文件小不了多少 是的，这个思路存在的问题是重复值怎么处理，所以不能在数组中仅存0或1，至少存储的是每个数字对应的个数才对，那么假如这个个数大于127怎么办？如果用这种方式存储的话，就需要定义一个长为2^32的int类型数组才对，，这的确是需要很大的内存才对。 如果看到我上一个回答的话，就会发现这个思路就是其中说过的利用索引的方式，这个方式的问题就是映射的数据结构本身也很大。另外，在我提出的思路中，将定义的1024x1024的数据改为2^32长度，那么这两种思路的效果就会一样了（可能都是运行不下去...） 原来是BIT数组，都吓了我一大跳，还以为向量是那样的，而且还可以用一个向量来表示10G多的整数。 |
| 返回顶楼 | |
|
发表时间：2010-04-06
一个可以保证最坏运行时间为O(n)的算法.
这个问题的通用形式为: 给定n个未排序的数字集合，找出第K小的数 这里即为找出第n/2小的数 一个可以保证最坏运行时间为O(n)的算法，叫做 "Median of Medians algorithm" 该算法的步骤比较简单: 设未排序数字个数为n 1.将这n个元素分为5个一组，找出每组里的中间数，形成新的n/5个中间值组成的集合 2.对这n/5亿个值再分为5个一组，找出每组中间的数...重复这些步骤，只至找的到最后的中间值m 3.以m为中值，将n个数分为L,R两组，L里的数都小于m,R里的数都大于m 如果m=n/2，则返回m 否则 如果L集合里的数多余一半，则从L集合中找出第n/2小的数 如果R集合里的数多余一半，R集合的元素个数为k, 则从R集合中找出第k-n/2小的数. 4.如此重复迭代调用，直至找到中值. 这类问题的通用解决方法由Blum, Floyd, Pratt, Rivest, and Tarjan 在1973年发表 叫做BFPRT, "Median of Medians algorithm" 也可看作BFPRT的一部分. BFPRT通常情况比"Median of Medians algorithm"快，但最坏情况下为O(n^2) 网上可以找到该算法实现的源代码,多为内存排序,但也比较容易改为外排序. Blum, Floyd, Pratt, Rivest, and Tarjan发表的论文是"Time bounds for selection" 网上可以下到这篇文章 |
| 返回顶楼 | |
|
发表时间：2010-04-06
xinyulou 写道 提烟而过 写道 xinyulou 写道 这个简单,只需要从头读取然后插入另一个文件,维持中间位数即可,几行代码搞定!
这位仁兄，你太牛了，能否把你的几行代码贴出来让大家共同拜读一下。这里是10G，你拷贝一个还算可行，如果是100G或更大呢，你安排怎么处理的?还有你是怎么在另一个文件中去维持中位数是哪个，是否可以给出你的思路? 哈哈,如果这个问题再加一个条件:只有1M的内存怎么办呢? 首先数据的表示方法要变化一下,用向量来表示整数集合,比如集合{1,3,4,5}可以表示为 010111 第一步,初始化所有位为0,n为多少位,如果位太多可以以文件的形式,文件的第几位.... for [0,n) bit[n] = 0; 第二步,读取源文件,把相应的位置1 for each i in input file bit[i] = 1; 第三步,输出 , 都是排好序的 for [0,n) if(bit[i] == 1) write i on output file 如果有重复数据要处理一下,一样存在两外一个文件里,第几位好多少个,输出的时候判断一下即可 貌似应该差不多了 如果最大数据比较小是个好方法。先不考虑重复数据吧。而且，第一次遍历时，先记下有多少个数据。 不过，有个问题，如果数据很大，最大的数极大，那么，你这生成的文件都超过 10G 了，说不定是 1000G。 |
| 返回顶楼 | |
|
发表时间：2010-04-06
最后修改：2010-04-06
10G的整形大概有25亿个整形,想从里面找寻中位数,我有一个最多32n的方法
1.每个数对首位进行异或运算(不懂异或的不用看了)并计2个数量,分别代表了[-2^31~~-1]和[0~2^31-1]的数量,假定为15亿个正数(假定包括0)和10亿个负数,那么答案在[0~2^31-1]范围内 2.哪堆数量比较多,就记录首位数字a(0代表正数,因此a=0),第二遍历的时候就首先满足首位是刚才记录的a,然后再对第二位进行异或运算,并计2个数量,代表了[0~2^30-1]和[2^30~2^31-1]的数量,假定为10亿和5亿,那么答案在[2^30~2^31-1]范围内 3.跟第2步一样,除了首先满足的条件是首位和第2位是0和1(看不懂?整数01开头的整数就代表[2^30~2^31-1]的范围) 4....... 5....... ....... 为什么说是最多32次?因为整数是由32位组成的 为什么说是最多?因为一旦判断不出中位数在哪堆范围内,只需要再来一次,计算这两堆数比较小的堆最大数,和较大堆的最小数,加一下除以2,那就是中位数 到最后一次的话,满足前31位相同,那么就只剩2个数,只要两个数都存在,加一下除以2就是答案,不然??就是那个只存在的数 PS:这里有一点要注意,如果一开始计数时,有一堆超过了整数大小就会导致程序不准确,应该用long型计数 (全思路完结) |
| 返回顶楼 | |
|
发表时间：2010-04-06
最后修改：2010-04-06
两次遍历就能解决问题，为什么还那么长篇大论、把简单问题复杂化。数据量大，全部装入内存装不下就用内存映射文件呀。
|
| 返回顶楼 | |
|
发表时间：2010-04-08
lyw985 写道 10G的整形大概有25亿个整形,想从里面找寻中位数,我有一个最多32n的方法
1.每个数对首位进行异或运算(不懂异或的不用看了)并计2个数量,分别代表了[-2^31~~-1]和[0~2^31-1]的数量,假定为15亿个正数(假定包括0)和10亿个负数,那么答案在[0~2^31-1]范围内 2.哪堆数量比较多,就记录首位数字a(0代表正数,因此a=0),第二遍历的时候就首先满足首位是刚才记录的a,然后再对第二位进行异或运算,并计2个数量,代表了[0~2^30-1]和[2^30~2^31-1]的数量,假定为10亿和5亿,那么答案在[2^30~2^31-1]范围内 3.跟第2步一样,除了首先满足的条件是首位和第2位是0和1(看不懂?整数01开头的整数就代表[2^30~2^31-1]的范围) 4....... 5....... ....... 为什么说是最多32次?因为整数是由32位组成的 为什么说是最多?因为一旦判断不出中位数在哪堆范围内,只需要再来一次,计算这两堆数比较小的堆最大数,和较大堆的最小数,加一下除以2,那就是中位数 到最后一次的话,满足前31位相同,那么就只剩2个数,只要两个数都存在,加一下除以2就是答案,不然??就是那个只存在的数 PS:这里有一点要注意,如果一开始计数时,有一堆超过了整数大小就会导致程序不准确,应该用long型计数 (全思路完结) 这个思路基本不花内存吧？而且时间复杂度也是 O(n)的，按理说是一个很完美的解决方案，怎么会没人顶的？？ |
| 返回顶楼 | |
