Чтобы уменьшить временную сложность

Question

У меня возник вопрос, в котором мне задан набор значений SET A и набор значений SET B. Я должен найти максимальное количество пар, которые могут принимать одно значение из множества A и одно значение с множеством В. Состояние- разница между этими двумя значениями должна быть меньше, чем 11.

SET EG-А-2,3,4 SET B-14,12,250 Max пар (possible- 14,4) и (12,3) ПРИМЕЧАНИЕ. (12,4) также может быть парой, но тогда она не даст нам максимально возможных наборов, так как 3 будет оставлено. Поэтому два достигают максимума 4 пары вверх с 14 и 12 с 3.

Я могу решить этот вопрос в сложности O (n^2), я искал лучшее решение.

Answer 1

Я ответил similar question 10 минут назад. Иды здесь одно и то же: петля над отсортирована диапазонов.

Вот тот же код, как и в другом ответе, адаптированный к вашей проблеме (я просто заменил равенство меньшего, чем отношение):

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.