寻找不同值的整数对(Finding number of pairs of integers differing by a value)

寻找不同值的整数对(Finding number of pairs of integers differing by a value)

如果我们有一个整数数组，那么除了O（n ^ 2）之外，是否还有其他有效方法可以用来找出相差给定值的整数对数？ 例如，对于数组4,2,6,7，相差2的整数对数是2 {（2,4），（4,6）}。 谢谢。

If we have an array of integers, then is there any efficient way other than O(n^2) by which one can find the number of pairs of integers which differ by a given value? E.g for the array 4,2,6,7 the number of pairs of integers differing by 2 is 2 {(2,4),(4,6)}. Thanks.

最满意答案

从列表中创建一个集合。 创建另一个集合，其中所有元素都由增量增加。 相交两组。 这些是你的配对的上限值。

在Python中：

>>> s = [4,2,6,7] >>> d = 2 >>> s0 = set(s) >>> sd = set(x+d for x in s0) >>> set((x-d, x) for x in (s0 & sd)) set([(2, 4), (4, 6)])

创建集合是O（n）。 相交的集合也是O（n），所以这是一个线性时间算法。

Create a set from your list. Create another set which has all the elements incremented by the delta. Intersect the two sets. These are the upper values of your pairs.

In Python:

>>> s = [4,2,6,7] >>> d = 2 >>> s0 = set(s) >>> sd = set(x+d for x in s0) >>> set((x-d, x) for x in (s0 & sd)) set([(2, 4), (4, 6)])

Creating the sets is O(n). Intersecting the sets is also O(n), so this is a linear-time algorithm.