两个排序数组中的最大对数

Question

这不是一个原始问题。我遇到了一个复杂的问题，现在简化为以下问题：

有两个排序数组，A和B，其中m和n分别为 元素，m = \Theta(n) 在 o(mn) 时间内运行的算法能否找到满足 A[i]-B[j] <= T 的最大对数，其中 T 是某个持续的？这怎么能做到呢？

编辑：

1. 这些对应该是不相交的，即一个元素最多只能被选择一次。

2. 算法应该在little-o(mn)内运行，这意味着在mn时间内运行的解决方案是不可接受的。

3. 是否也可以找到我们选择的对？

说明：

如果数组是 a_1, a_2, ..., a_m 和 b_1, b_2, ..., b_n，我需要找到对 (a_i, b_j) 使得 |a_i - b_j| <= T。不允许多次选择一个元素。我们怎样才能最大化给定数组的对的数量？

Answer 1

更新2：

更新后的问题（仅使用任一数组中的元素一次，获取对，并且值的绝对差必须低于T）可能能够在O(n+m)时间内完成。我还没有充分考虑下面的算法来决定它是否总是获得最大数量的对，但在大多数情况下应该：

int i = 0;
int j = 0; 

while(i < A.length){
    while(j < B.length){
        if(A[i]-B[j] <= T){
            if(A[i]-B[j] >= -1 * T){
                addPair(i, j);
                j++;//don't consider this value the next time
            }
            break;
        } 
        j++;
    }
    i++;
}

Answer 2

在O(n lg n) = O(m lg m)中：根据A的元素创建平衡二叉搜索树，并在每个节点中存储a的索引元素和元素值。对于B的每个元素，搜索小于或等于B[j] + T的最大值。这个数字的索引会告诉你有多少个数字小于或等于这个数字。

Answer 3

如果您想要匹配|A[i]-B[j]|的对的数量<= T，其中每个 A[i] 和 B[j] 在所有对中仅使用一次：

int lastB = 0;
int result=0;
for(int a = 0; a<A.size(); ++a) {
    const int minB = A[a] - T;  
    while(lastB<B.size() && B[lastB] < minB)
        ++lastB;
    const int maxB = A[a] + T;
    if (lastB<B.size() && B[lastB] > minB) {
        ++lastB;
        ++result;
    }
}
return result;

此算法扫描 中的最小范围>B，并确保 B 中没有元素被使用两次。