Учитывая массив целых чисел, каков наиболее эффективный способ получить число других целых чисел в массиве в пределах 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);

Простой цикл foreach - это путь? 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

Мой последний ответ был написан без полного решения проблемы...

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

$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