如何找到差异小于特定值的最大对数？

一尘不染

如何找到差异小于特定值的最大对数？

algorithm

我得到了两个包含正整数的数组（可以包含重复项和相同长度的数组）。当两个数组中的数字只能使用一次时，我必须找到绝对差小于特定值（给定）的最大对数。

例如：

arr1 = {1,2,3,4}
arr2 = {8,9,10,11}
diff = 5

那么，可能的对是（3,8），（4,8）。也就是说，只有两个这样的可能对。

输出应为2。

另外，我可以想到O（n ^
2）中的一种算法。但是，我需要更好的东西。我想到了哈希映射（因为数组包含重复项，因此无法正常工作），想到以降序和升序对数组进行排序，实际上并不能从那里继续前进。

阅读 261

2020-07-28

共1个答案

一尘不染

通常的想法是遍历排序范围。这样，您就可以降低O(N^2)通常的蛮力工作O(N log N)。

这是伪代码中的一种算法（也许稍后我将使用真实的C ++代码进行更新）：

对两个数组进行排序
使用两个迭代器同时循环两者：
1. 如果找到一对，将其插入您的列表。增加两个迭代器。
2. 否则，增加指向较小元素的指标。

总体而言，这主要取决于平均所需的排序O(N log N)。

这是承诺的代码：

auto find_pairs(std::vector<int>& arr1, std::vector<int>& arr2, int diff)
{
    std::vector<std::pair<int,int> > ret;

    std::sort(std::begin(arr1), std::end(arr1));
    std::sort(std::begin(arr2), std::end(arr2));

    auto it1= std::begin(arr1);
    auto it2= std::begin(arr2);

    while(it1!= std::end(arr1) && it2!= std::end(arr2))
    {
        if(std::abs(*it1-*it2) == diff)
        {
            ret.push_back(std::make_pair(*it1,*it2));
            ++it1;
            ++it2;
        }
        else if(*it1<*it2)
        {
            ++it1;
        }
        else
        {
            ++it2;
        }
    }

    return ret;
}

它将两个向量的匹配元素作为的向量返回std::pairs。对于您的示例，它会打印

3  8
4  9

演示

2020-07-28