HardBirch

用bitmap实现中位数的算法

时间:10-05-07 栏目:HTML5移动开发 作者:张飞不张,文采横飞 评论:4 点击: 2,575 次

常见面试题之一:50亿个整数,内存限制为1G,找出中位数。

50亿个整数用bitmap来存储的话,大约150M的空间就足够了。

下面是具体的算法,用PHP实现。

 

 

 

 

声明: 本文由( 张飞不张,文采横飞 )原创编译,转载请保留链接: 用bitmap实现中位数的算法

用bitmap实现中位数的算法:目前有4 条留言

  1. 4楼
    remox:

    $temp = (1 << ($i & MASK));

    这句是什么意思
    按我的理解 $temp= ($i & MASK));
    不应该再有移位才对,上面这样temp 一定会溢出的啊

    2010-08-29 16:16 [回复]
  2. 地板
    remox:

    明白了 我错了~

    2010-08-29 16:19 [回复]
  3. 板凳
    clseer:

    前提是50亿整数不重复?

    2011-05-22 10:11 [回复]
  4. 沙发
    njusthsy:

    我觉得必然存在问题:bitmap要求数据不重复,而对于32位整数,最多也才2^32=40亿个不同的数;可见,这50亿个数必然存在重复的,bitmap法有问题[e07]

    2011-05-24 22:32 [回复]

发表评论


QQ群互动

Linux系统与内核学习群:194051772

WP建站技术学习交流群:194062106

魔豆之路QR

魔豆的Linux内核之路

魔豆的Linux内核之路

优秀工程师当看优秀书籍

优秀程序员,要看优秀书!

赞助商广告

友荐云推荐