为了降低时间复杂度

Question

我有一个问题，我得到了一组值 SET A 和一组值 SET B。我应该找到最大可能的对数，从 A 组中取一个值，一个值是设置 B。健康）状况- 两个值之间的差异应小于 11.

例如- 设置 A-2,3,4 SET B-14,12,250 最大对可能 - (14,4) 和 (12,3) 注意-(12,4) 也可以是一对，但是它不会给我们最大可能的集合，因为还剩下 3 个。因此两个达到最大 4 对 14 和 12 与 3.

我能以 O(n^2) 的复杂度解决这个问题，我一直在寻找更好的解决方案。

Answer 1

我在 10 分钟前回答了。这里的ides是一样的：循环遍历sorted ranges.

这是针对您的问题改编的其他答案中的相同代码（我只是用小于关系替换了相等性）：

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

这是您示例的应用程序，

int main()
{

    std::vector<int> arr1 = {2,3,4};   
    std::vector<int> arr2 = {14,12,250};   
    int diff=11;

    auto pairs = find_pairs(arr1, arr2, diff);

    for(auto& i : pairs)
    {
        std::cout<<i.first<<"  "<<i.second<<std::endl;
    }    
}

通过这个获得 OP 中给出的所需答案：

2  12
4  14

DEMO.

为了降低时间复杂度

To reduce the time complexity

c++

dynamic-programming

divide-and-conquer