c++ - 用于查找范围重叠的内存效率更高的算法

Question

在this问题，答案包括一种算法，用于查找给定范围内范围列表的重叠。但在我的情况下，我有一个 n 整数列表，当将其分组为 n^2 对时形成范围。例如，如果我们从整数数组中获取 array[i] 和 array[j]，(array[i]-array[j],array[i ]+array[j]) 做一个范围。但是为了实现建议的算法，解决方案的内存复杂度为 O(n^2)。是否可以进一步优化(在内存方面)？

例子: 我有一个更大的范围 (l,r)，我必须找到 (l,r) 中至少有多少整数位于范围列表中的任何一个范围内.例如，给定的整数数组是{1,2,3}。所以所有可能的范围都是(2-1,1+2), (3-1,1+3), (3-2,3+2)。假设 (l,r) 是 (2,7)。那么因为 (2,5) 至少存在其中一个 4 就是答案。

Answer 1

首先对数组进行排序(如果尚未排序)。然后请注意，唯一值得考虑的范围是 j == i-1 .

要理解为什么考虑以下数组:

{2,3,5,8}

那么可能的范围是:

i=3 j=2 ==> (8-5,8+5) = (3,13)
i=3 j=1 ==> (8-3,8+3) = (5,11)
i=3 j=0 ==> (8-2,8+2) = (6,10)

i=2 j=1 ==> (5-3,5+3) = (2,8)
i=2 j=0 ==> (5-2,5+2) = (3,7)

i=1 j=0 ==> (3-2,3+2) = (1,5)

请注意 j < i-1 的范围始终是 j == i-1 范围的严格子集，因此不需要考虑这些范围。所以你只需要考虑 O(n) 个范围。