<分区>
给定一个整数对数组 pair<int,int> , 需要找到 pair<> 的对数使得对的第一个元素之间的绝对差小于或等于对的第二个元素的最小值。
例如:
Pair 1: 2,5
Pair 2: 7,4
Since (7-2) <= min(5,4) it is a valid pair
PS:我期待比天真的时间复杂度更好的 O(N*N) .
<分区>
给定一个整数对数组 pair<int,int> , 需要找到 pair<> 的对数使得对的第一个元素之间的绝对差小于或等于对的第二个元素的最小值。
例如:
Pair 1: 2,5
Pair 2: 7,4
Since (7-2) <= min(5,4) it is a valid pair
PS:我期待比天真的时间复杂度更好的 O(N*N) .
最佳答案
让我们按非递增顺序按第二个值对我们的对进行排序。然后按此顺序遍历对。假设当前对的索引为 i , 并查看所有对 (j, i) , 其中j < i .我们知道这些对中第二个元素的最小值是 pairs[i].second (因为非递增顺序)。然后我们需要找到索引的数量 j在哪里
|pairs[j].first - pairs[i].first| <= pairs[i].second
让我们重新表述:我们需要找到索引为 j < i 的对的第一个元素的数量位于区间内:
[pairs[i].first - pairs[i].second, pairs[i].first + pairs[i].second]
例如，这可以通过 augmented self-balancing BST 来完成(我们可以在 O(log(n)) 中保留和更新每个顶点中的 child 数量) .
伪代码:
res = 0
sort pairs by second value in non-increasing order
for i = 1 to n
res += number of elements in BST on interval [pairs[i].first - pairs[i].second, pairs[i].first + pairs[i].second]
add pairs[i].first to BST
整体复杂度为 O(n*log(n)) .
如果对中的整数值为 O(n) , BST 可以替换，例如，用 Fenwick tree或 Segment tree .
关于c++ - 第一个元素之间的差异小于或等于第二个元素的最小值的对数对，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48504951/