用bitmap实现中位数的算法

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

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

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

define("MASK", 0x1f);$source = array(1, 74, 4, 256, 1024, 110, 111, 112, 123, 112, 100);$array = array();$count = 0;foreach($source as $num) {set($num); // add to bit map}$count = intval($count >> 1) + 1; // cal middle numberfor($i = 0;;$i++) { // travel the bit map and find the middle number$num = $array[$i];if(!$num) {continue;}$sum = 0;while($num) {if($num & 0x1) {if(!--$count) {echo ($i <<5) + $sum;exit;}}$num >>= 1;$sum++;}}/* * set number to bit map */function set($i) {global $array;global $count;$temp = (1 <<($i & MASK));$array[$i >> 5] |= $temp;if($temp) {$count++;}}