|
锁定老帖子 主题：一道腾讯面试题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (1) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-04-09
lyw985 写道 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)的，按理说是一个很完美的解决方案，怎么会没人顶的？？ 好像不是这个思路，这个思路计算出来的是分布最密集的那个数，但不一定是中位数。 |
| 返回顶楼 | |
|
发表时间：2010-04-10
蔡华江 写道 好像不是这个思路，这个思路计算出来的是分布最密集的那个数，但不一定是中位数。
对于中位数的定义，我想你应该清楚的吧 我这个算法的重点在于，不对数字进行储存，不耗内存，只记录了某个范围值的个数，结合整数是由32位组成的特性，准确定位排完序后最中间的数，有任何疑问，欢迎拍砖 |
| 返回顶楼 | |
|
发表时间：2010-04-10
lyw985 写道 蔡华江 写道 好像不是这个思路，这个思路计算出来的是分布最密集的那个数，但不一定是中位数。
对于中位数的定义，我想你应该清楚的吧 我这个算法的重点在于，不对数字进行储存，不耗内存，只记录了某个范围值的个数，结合整数是由32位组成的特性，准确定位排完序后最中间的数，有任何疑问，欢迎拍砖 一致性hash算法么。 |
| 返回顶楼 | |
|
发表时间：2010-04-10
抛出异常的爱 写道 一致性hash算法么。
应该跟一致性hash算法不一样，一致性hash算法应该不会记录重复的个数的？？ 不知道一致性hash算法，纯粹猜想 
|
| 返回顶楼 | |
|
发表时间：2010-04-10
lyw985 写道 抛出异常的爱 写道 一致性hash算法么。
应该跟一致性hash算法不一样，一致性hash算法应该不会记录重复的个数的？？ 不知道一致性hash算法，纯粹猜想 假设有一个2^32个虚节点 把集合统计点放在几个虚节点之上使其成为实节点 如果命中的是虚节点就向下遍历到下一个实节点 加到实节点之上 实节点只要统计总数量就可以了 如果要增加就在 在两个实节点之间加入几个实节点进行定位。 如果要减少把实节点拷贝到下一个实节点之上 
|
| 返回顶楼 | |
|
发表时间：2010-04-10
最后修改：2010-04-10
抛出异常的爱 写道 假设有一个2^32个虚节点
把集合统计点放在几个虚节点之上使其成为实节点 如果命中的是虚节点就向下遍历到下一个实节点 加到实节点之上 实节点只要统计总数量就可以了 如果要增加就在 在两个实节点之间加入几个实节点进行定位。 如果要减少把实节点拷贝到下一个实节点之上 仔细看了下，发现我的算法跟hash算法仍然不能匹配起来 抛出异常的爱 写道 如果命中的是虚节点就向下遍历到下一个实节点
这句话明显跟我的算法有差异，如果说所谓的向下遍历的方式包括我所说的异或运算， 那么跟hash算法还是有相似的地方 |
| 返回顶楼 | |
|
发表时间：2010-04-10
最后修改：2010-04-10
抛出异常的爱 写道 随机找到个数
把数据重排一下 大于这数的放左 小于这数的放右 少的部分变成一个箱的总个数其它不管 多的那边再生成两个箱 每次计算出来中值可能在哪个箱中 就拆哪个箱子 左右摆动直到中间的数组足够小。。。。 这个复杂度是 O(n*lgn) 我发现我的算法跟你的算法差不多，只要你 1.不储存内容， 2.不随机挑选，而选择范围中间那个数 方法跟我可以说是一摸一样， 由于你随机挑数，所以你的复杂度比我高一个层次 |
| 返回顶楼 | |
|
发表时间：2010-04-10
lyw985 写道 蔡华江 写道 好像不是这个思路，这个思路计算出来的是分布最密集的那个数，但不一定是中位数。
对于中位数的定义，我想你应该清楚的吧 我这个算法的重点在于，不对数字进行储存，不耗内存，只记录了某个范围值的个数，结合整数是由32位组成的特性，准确定位排完序后最中间的数，有任何疑问，欢迎拍砖 我知道你这算法的优点，我只是认为你以上列出来的算法计算出来的不是中位数而已。因为在计算第一位时，是分辩出了中位数是处于正数还是负数。而在分析第二位时开始出现偏差，因为你只是认为第二位时，数量偏多的那位中应当包含中位数。我的意见是不然的，因为你忽略了你已经分离出来的那些负数。。。所以我认为这个思路是有偏差的。 当然，我想，如果你将定位为查询第几个数时，那么每次记录当前所有数据相对于原有记录集合的偏移，那么记录的结果才是正确的。比方：总集合为25亿，当计算第一位时，分辨出中位数在正数中，且已分离出负数12亿位。计算第二位时，我们要找的就不仅仅是数量最多的那个集合，而是找在开始地方1亿处的数据。。。当然，算法的前提是你需要知道总共有多少数据，这不难得到，但是需要遍历数据。。。。 |
| 返回顶楼 | |
|
发表时间：2010-04-10
最后修改：2010-04-10
不知道你有没有看到过我的前面的一个回答http://www.iteye.com/topic/630831?page=3#1438839，跟你这个有异曲同工之处，也是不对数字进行储存，不耗内存，只记录某个数的范围。
这个帖子只描述了实现方式，可能没有说清原理，大家都没有关注。其解决思路由浅出来讲，，如果100都是100以下的数，那么可以分为0-10，11-20.。。。91-100几个部分，分别个数为11、12、8、9、6、14、15、14、5、6，我们只要判断每堆数目的个数，我们就可以判定该数是在51-60之间，且右边要住左偏移6位数，那么中位数就是51-60间排序好去掉右边6位数后求出的中位数。 同样50亿的数目也可以划分为0。。9十个部分，甚至0.。。1024一千多个部分或0。。1024x1024的一百万堆数据，，。我们只需要根据每堆中的个数来判断该中位数是处在那一堆数据中，或者有可能是那两堆数据中。。。这样来说，我们只需要选择一个适合的大小来存储每堆数据的个数，只需要遍历一次数据用来取得每堆数的个数，，遍历第二次用来取得符合那一堆大小的数据再来进行处理。。 这个方法用来进行数据大小的依据同样是位运算，在不考虑负数的情况下，将数据右移20位就可以划分为1024x1024个数组。 在我的机器上我进行过一次测试，读取一亿的数据量是不怎么需要内存的。。 |
| 返回顶楼 | |
|
发表时间：2010-04-10
蔡华江 写道 因为你忽略了你已经分离出来的那些负数 我的例子中并没有忽略分离出来的那些负数， 我的例子是，正数15亿，负数10亿， 然后遍历，分出10亿和5亿， 照你的意思，我忽略了我已经分离出来的那些负数，应该选择10亿 但是我选择了5亿，因为我没有忽略 |
| 返回顶楼 | |
