Question

100万个32位整数，如何最快找到中位数.能保证每个数是唯一的，如何实现o算法

Answer 1

比如 1-9 这9个数字的中位数是 5

这些数的和是 45
temp = 5*0.618=3.09
比如现在的顺序是 189234675
然后郑帆 temp每次修正　temp= temp * n/2(n-m) n是 数组 个数 m 是 小于 temp 的 个数
一搜茄遍下来 big = {8,9,4,6,7,5}
samll = {1,2,3}
现在 修正 temp = 3.09*9/6 =4.635

一遍下来 big = {8,9,6,7,5}
samll = {1,2,3,4}
temp = 4.635*9/8=5.214375

一遍下来 big = {8,9,6,7}
samll = {1,2,3,4,5}
temp = 5.214375 * 9/8

边界是 count(big) - count(samll) < =1
这样 最后 可以得到 中位数 但是 效率
不高

用的 原来就是 中位数 的 大于他的 和小于他的 个数 一样

对应算法是 search_zhong.php

<?php
$arr = array();//定义数组
for($i=0;$i<=1000;$i++){//假设有 1001个数字 现在随机生成
$arr[] = rand(0,10000);
}
$arr_s = $arr;
$time = time();//排序前开始计时
sort($arr);//对数组 排序

$zhongwei = $arr[501];//中位数
echo '中位数喊漏雹是：'.$zhongwei.'找到中位数用了'.time()-$time.'秒
';
$time2 = time();

echo '中位数是：(用马乙说的方法)'.mayiFunc($arr_s,0,0).'找到中位数用了'.time()-$time2.'秒
';

function mayiFunc($arr,$temp,$m){
$n = count($arr);
if($temp == 0){
$sum = array_sum($arr);
$agv = $sum/count($arr);
$temp = $agv*0.618;
}else{
$temp = $temp * $n/(2*($n-$m));
}

$big = array();
$small = array();
foreach($arr as $a){
if($a>$temp){
$big++;
}
else{
$small++;
}
}
if($big>$small){
if($big-$small<=1){
echo $temp;
exit;
return $temp;
}
else{
mayiFunc($arr,$temp,$small);//迭代调用
}
}else{
if($small-$big<=1){
echo $temp;
exit;
return $temp;
}
else{
mayiFunc($arr,$temp,$big);//迭代调用
}
}

}

这样感觉效率还是不高！