计算有效配对的问题可以在排序时间+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个数字,该数字在索引4处为8。因此,output [1] = 4。-20无法与任何内容配对,因此output [0] = 6(越界)。另一个例子:output [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
在我们的示例中,这段代码会给出(array 和 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个配对,对应索引为8。另一个细节是,这个算法会计算自身配对,如果不想要,就需要减去自身配对的数量。例如,3似乎包含了3-2+1=2个配对,分别在索引2和3处。当然,3本身在索引2处,所以其中一个是自身配对,另一个是与4的配对。只要output和output2的索引范围包含正在查找的索引本身,就需要减去1。在代码中,可以这样写:
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
for j in range(i+1, len(array)):
(这也意味着你不需要if i != j
) - jcfollower