用bitmap实现中位数的算法[ZT]
用bitmap实现中位数的算法[ZT]
http://blog.csdn.net/hfahe/archive/2010/05/07/5567259.aspx
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 number
for($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++;
}
}