给定一个整数数组，获取 n 以内数组中其他整数数量的最有效方法是什么? - Given an array of integers, what's the most efficient way to get the number of other integers in the array within n?

Given an array of integers, what's the most efficient way to get the number of other integers in the array within n?

给定以下数组：

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

假设$n = 2，在每个值的$n内获取数组中每个值的计数的最有效方法是什么？

例如，6 在 $n 中有 3 个其他值：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循环是要走的路吗？代码板链接

$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);

我的最后一个答案是在没有完全摸索问题的情况下写的......

在处理数组之前，请尝试对数组进行排序，并在运行数组时利用它。这具有更好的运行时复杂性。

$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