如何找到差值小於特定值的最大對數？

我給出了包含正整數的兩個數組（可以包含重複項和相同長度）。當數字只能在兩個數組中使用一次時，我必須找到絕對差異小於等於特定值（給定）的最大對數。如何找到差值小於特定值的最大對數？

例如：

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

如何找到差值小於特定值的最大對數？

回答

相關問題