爲了減少時間複雜度

Question

我在這，我給一組值的集合A的問題時，和一組值集合B的我應該找採取從，設置一個值對可能的最大數量，一個值與組B. 條件 - 兩個值之間的差應小於11

EG- SET A-2,3,4- SET B-14,12,250 最大成對possible-（ 14,4）和（12,3） 注意 - （12,4），也可以是一對，但隨後，它不會給我們最大的可能集，3會留下。爲此兩次與3

我能夠解決o這個問題（N^2）的複雜性，我一直在尋找一個更好的解決方案實現最大4對了14和12。

Answer 1

我回答了similar question 11分鐘前。這裏的ide是一樣的：循環結束排序範圍。

下面是相同的代碼，如適用於您的問題對方的回答（我只是換成了小於-關係的平等）：

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。