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

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

例如：

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

然后，可以对为（3,8），（4,8）。也就是说，只有两种这样的可能配对。

输出应该为2

另外，我能想到的算法中的此在为O（n^2）。但是，我需要更好的东西。我想过哈希映射（不会工作，因为数组包含重复项），想到按降序和升序对数组进行排序，并没有真正能够从那里向前移动。

来源

2015-06-20 John Lui

你的第二句话没写清楚。你的意思是：“我必须找到绝对差值小于或等于给定值的唯一对数。” –

是的，但是如果数字一旦用来组成一对，他们就不能再次使用。 –

我正在投票结束这个问题，因为这是一个正在进行的竞争，将在一天内完成。 –

通常的想法是循环排序范围。这样，你可以通过O(N log N)来降低蛮力O(N^2)的努力。

下面是在伪代码的算法（也许我会与真正的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

DEMO

来源

2015-06-20 20:27:54 davidhigh

伟大的算法。很容易理解。完美的作品。谢谢 –

其实我认为这是行不通的。检查'arr1 = [1 2 3 4]''arr2 = [1 2 3 4]''diff = 5'从我的理解中应该给出16对。 – Tempux

@ sudomakeinstall2您的反驳意见不是很清楚，请您详细说明。 – Steephen

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

回答

相关问题