给定 N 个整数，计算差为 K 的整数对的数量

Question

我得到了一个这样的数组array(1,5,3,4,2);
说 k=2，我应该找出差为 2 的对数。在这种情况下，它应该 return 3 因为 5-3, 4-2, 3-1

这是我试过的方法。它工作正常我正在遍历数组两次 O(n^2) 复杂性，我想知道是否有更好的方法来实现这一点。

$arr = array(1,5,3,4,2); 
$k =2;
function find_pairs($arr, $k)
{
    $count = 0;
    for ($i=0 ; $i<= count($arr)-1 ; $i++)
    {
        for ($j=$i+1; $j <= count($arr)-1 ; $j++)
        {
            if ($arr[$i]-$arr[$j] == $k || $arr[$j]-$arr[$i]==$k)
            {
                $count++;
            }
        }
    }
    return $count;
}
echo find_pairs($arr, $k);

谢谢

Answer 1

当然有很多方法：

使用排序：

Sort the array arr
Take two pointers, l and r, both pointing to 1st element
Take the difference arr[r] – arr[l]
If value diff is K, increment count and move both pointers to next element
if value diff > k, move l to next element
if value diff < k, move r to next element
return count

复杂度为 O(n) 的是：

1) Initialize count as 0.
2) Insert all distinct elements of arr[] in a hash map.  While inserting, 
   ignore an element if already present in the hash map.
3) Do following for each element arr[i].
   a) Look for arr[i] + k in the hash map, if found then increment count.
   b) Look for arr[i] - k in the hash map, if found then increment count.
   c) Remove arr[i] from hash table.

无论如何，您可以参考此 link 了解更多信息。

Answer 2

当然可以。以下是您可以使用的内容：

排序数组（a，say 和 n 个元素）
为索引 0 到 n-2 的所有元素搜索（二进制）a[i]+k。成功点击次数就是你的答案。

复杂度为 O(n log n)。

Answer 3

是的。您可以使用 unordered_set。详细说明如下：

1. Insert the all elements of array into unordered_set.
2. Initialize count=0
3. for loop i=0 to i=n where n is the length of array
         if arr[i]+k is found then increment count
4. Return count.

上述过程的复杂度为O(N)。

Php 代码片段：

function find_pairs($a, $k) 
{
    $num = array_flip($a);
    $count = 0;
    foreach($num as $n => $_unused) 
    {
        if(isset($num[$n + $k])) 
        {
            $count++;
        }
    }
    return $count;
}

Answer 4

给定一个整数 n，使用递归计算 return 给定整数中存在的零的数量。

def count0(n):
    if n==0:
        return 0
    if n%10==0:
        return 1+count0(int(n/10))
    else:
        return count0(int(n/10))

n=int(input())
print(count0(n))

给定 N 个整数，计算差为 K 的整数对的数量

Given N integers, count the number of pairs of integers whose difference is K

php

arrays

time-complexity