如何在整数数组中找到所有有序元素对,其总和位于给定的值范围内

Question

给定一个整数数组,找到数组中所有有序元素对的数量,其总和位于给定范围[a,b]

这是一个O(n ^ 2)解决方案

'''
counts all pairs in array such that the 
sum of pair lies in the range a and b
'''
def countpairs(array, a, b):
    num_of_pairs = 0
    for i in range(len(array)):
        for j in range(i+1,len(array)):
            total = array[i] + array[j]
            if total >= a and total <= b:
                num_of_pairs += 1
    return num_of_pairs

我知道我的解决方案不是最优的.做这个的更好算法是什么.

Answer 1

1. 对数组进行排序(按升序排序).
2. 对于数组中的每个元素x:
   • 考虑元素后面的数组切片.
   • 在[a - x]的数组切片上进行二进制搜索,将其称为y0.如果没有找到精确匹配,考虑最接近的匹配更大的比[A - X]为Y0.
   • 只要x + y <= b,就从y0向前输出所有元素(x,y)

时间复杂度当然是输出敏感的,但这仍然优于现有的算法:

O(nlogn) + O(k)

其中k是满足条件的对的数量.

注意:如果您只需要计算对的数量,则可以执行此操作O(nlogn).修改上述算法,以便搜索[b - x](或下一个较小的元素).这样,您可以O(logn)简单地从第一个和最后一个匹配的索引计算每个元素具有的"匹配"数.然后,这只是一个总结得到最终计数的问题.这样,初始O(nlogn)分选步骤占主导地位.

Answer 2

首先对数组进行排序,然后按两个索引计算对.两个索引的方法类似于二和问题中的一个,这避免了二次搜索的N次数.该算法的耗时Sort Complexity + O(N)通常是排序为O(NInN),因此该方法是O(NInN).对于索引i,该算法的想法是找到下限和上限,使得a <= arr[i]+arr[low] <= arr[i]+arr[high] <= b当i增加时,我们应该做的是减少low并high保持条件.为了避免两次计算同一对,我们保持low > i,我们也保持low <= high.以下计数方法的复杂性是O(N),因为在while loop我们能做的是++i或者--low或者--high最多的是N 这样的行动.

//count pair whose sum is in [a, b]
//arr is a sorted array with size integers.
int countPair(int arr[], int size, int a, int b) {
    int cnt = 0;
    int i = 0, low = size-1, high = size?1;
    while (i < high) {
        //find the lower bound such that arr[i] + arr[low] < a, 
        //meanwhile arr[i]+arr[low+1] >= a
         low = max(i, low);
         while (low > i && arr[i] + arr[low] >= a) --low;

        //find an upper bound such that arr[i] + arr[high] <= b 
        //meanwhile, arr[i]+arr[high+1] > b
        while (high > low && arr[i] + arr[high] > b) --high; 
        //all pairs: arr[i]+arr[low+1], arr[i]+arr[low+2],...,arr[i]+arr[high]
        //are in the rage[a, b], and we count it as follows.
        cnt += (high-low);
        ++i;
    }
    return cnt;
}

Answer 3

计算工作对的问题可以在排序时间+ O(N)中完成.这比Ani给出的解决方案更快,即排序时间+ O(N log N).这个想法是这样的.首先你排序.然后,您运行几乎相同的单通道算法两次.然后,您可以使用两个单通算法的结果来计算答案.

我们第一次运行单遍算法时,我们将创建一个新数组,列出可以与该索引合作的最小索引,以得到大于a的总和.例:

a = 6
array = [-20, 1, 3, 4, 8, 11]
output = [6, 4, 2, 2, 1, 1]

因此,数组索引1处的数字是1(基于0的索引).它可以配对以获得超过6的最小数字是8,它在索引4处.因此输出[1] = 4. -20不能与任何东西配对,因此输出[0] = 6(越界) .另一个例子:输出[4] = 1,因为8(索引4)可以与1(索引1)或其后的任何数字配对,总和超过6.

你现在需要做的就是让自己相信这是O(N).它是.代码是:

i, j = 0, 5
while i - j <= 0:
  if array[i] + array[j] >= a:
    output[j] = i
    j -= 1
  else:
    output[i] = j + 1
    i += 1

想想从边缘开始并向内工作的两个指针.这是O(N).你现在做同样的事情,只是条件b <= a:

while i-j <= 0:
  if array[i] + array[j] <= b:
    output2[i] = j
    i += 1
  else:
    output2[j] = i-1
    j-=1

在我们的示例中,此代码为您提供(数组和b以供参考):

b = 9
array = [-20, 1, 3, 4, 8, 11]
output2 = [5, 4, 3, 3, 1, 0]

但是现在,output和output2包含了我们需要的所有信息,因为它们包含配对的有效索引范围.output是它可以配对的最小索引,output2是它可以配对的最大索引.差值+ 1是该位置的配对数.因此对于第一个位置(对应于-20),有5 - 6 + 1 = 0对.对于1,有4-4 + 1个配对,索引4处的数字为8.另一个微妙,这个算法计算自我配对,所以如果你不想要它,你必须减去.例如3似乎包含3-2 + 1 = 2对,一个在索引2,一个在索引3.当然,3本身在索引2,所以其中一个是自配对,另一个是与4配对只要输出和输出2的索引范围包含索引本身,你只需要减去一个' 看着.在代码中,您可以编写:

answer = [o2 - o + 1 - (o <= i <= o2) for i, (o, o2) in enumerate(zip(output, output2))]

产量:

answer = [0, 1, 1, 1, 1, 0]

哪个总和为4,对应于(1,8),(3,4),(4,3),(8,1)

无论如何,正如你所看到的,这是sort + O(N),这是最佳的.

编辑:要求完整实施.提供.供参考,完整代码:

def count_ranged_pairs(x, a, b):
    x.sort()

    output = [0] * len(x)
    output2 = [0] * len(x)

    i, j = 0, len(x)-1
    while i - j <= 0:
      if x[i] + x[j] >= a:
        output[j] = i
        j -= 1
      else:
        output[i] = j + 1
        i += 1

    i, j = 0, len(x) - 1
    while i-j <= 0:
      if x[i] + x[j] <= b:
        output2[i] = j
        i += 1
      else:
        output2[j] = i-1
        j -=1

    answer = [o2 - o + 1 - (o <= i <= o2) for i, (o, o2) in enumerate(zip(output, output2))]
    return sum(answer)/2

Answer 4

from itertools import ifilter, combinations

def countpairs2(array, a, b):
    pairInRange = lambda x: sum(x) >= a and sum(x) <= b
    filtered = ifilter(pairInRange, combinations(array, 2))
    return sum([2 for x in filtered])

我认为Itertools库非常方便.我还注意到你计算了两次对,例如你把(1,3)和(3,1)算作两种不同的组合.如果您不想这样,只需将最后一行中的2更改为1.注意:最后一行可以更改为return len(list(filtered)) * 2.这可以更快,但代价是使用更多的RAM.