寻找整数对一个值不同数量 [英] 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.

推荐答案

创建了一套从你的清单。建立另一套里面有所有的增量递增的元素。相交两组。这些是您对的上端值。

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.

在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），所以这是一个线性时间的算法。

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

这篇关于寻找整数对一个值不同数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！