Учитывая массив целых чисел, каков наиболее эффективный способ получить число других целых чисел в массиве в n?

Question

Учитывая следующий массив:

$arr = array(0,0,1,2,2,5,6,7,7,9,10,10); 

И если предположить $n = 2, что является наиболее эффективным способом, чтобы получить количество каждого значения в массиве в пределах $n каждого значения?

Например, 6 имеет 3 других значения в пределах $n: 5,7,7.

В конечном счете я хотел бы соответствующий массив просто подсчетов в $n, например, так:

   // 0,0,1,2,2,5,6,7,7,9,10,10 // $arr, so you can see it lined up 
$count_arr = array(4,4,4,4,4,3,3,4,4,4, 2, 2); 

Это простая Еогеасп петля путь? CodePad Link

$arr = array(0,0,1,2,2,5,6,7,7,9,10,10); 
$n = 2; 
$count_arr = array(); 
foreach ($arr as $v) { 
    $range = range(($v-$n),($v+$n)); // simple range between lower and upper bound 
    $count = count(array_intersect($arr,$range)); // count intersect array 
    $count_arr[] = $count-1; // subtract 1 so you don't count itself 
} 
print_r($arr); 
print_r($count_arr); 

Answer 1

Мой последний ответ был написан без полностью groking проблемы ...

Попробуйте сортировки массива, перед обработкой, и рычаги, которые при запуске через него. Это улучшает сложность выполнения.

$arr = array(0,0,1,2,2,5,6,7,7,9,10,10); 
asort($arr); 
$n = 2; 
$cnt = count($arr); 
$counts = array_pad(array(), $cnt, 0); 
for ($x=0; $x<$cnt; $x++) { 
    $low = $x - 1; 
    $lower_range_bound = $arr[$x]-$n; 
    while($low >= 0 && ($arr[$low] >= $lower_range_bound)) { 
     $counts[$x]++; 
     $low--; 
    } 
    $high = $x + 1; 
    $upper_range_bound = $arr[$x]+$n; 
    while($high < $cnt && $arr[$high] <= $upper_range_bound) { 
     $counts[$x]++; 
     $high++; 
    } 
} 
print_r($arr); 
print_r($counts); 

Играть с ним здесь: http://codepad.org/JXlZNCxW