java - 两个排序数组的最大对数

Question

这不是原始问题。我有一个复杂的问题，现在简化为以下内容:

有两个排序数组，A和 B与 m和 n元素分别为m = \Theta(n)可以在 o(mn) 中运行的算法吗？时间找到最大对数，使得 A[i]-B[j] <= T其中 T 是某个常数？如何才能做到这一点？

编辑:

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

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

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++;
}