Даны два массива a и b. Найдите все пары элементов (a1, b1), для которых a1 принадлежит массиву A, а b1 принадлежит массиву B, чья сумма a1 + b1 = k

Question

Я ищу решение следующего алгоритма с минимальной временной и пространственной сложностью.

Для двух массивов a и b найдите все пары элементов (a1, b1), для которых a1 принадлежит массиву A, а b1 принадлежит массиву B, чья сумма a1 + b1 = k (любое целое число).

Мне удалось придумать подход O (n log n), в котором мы отсортируем один из массивов, скажем, A, и для каждого элемента b в массиве B проведем двоичный поиск в отсортированном массиве A для значения (Кб). .

Можем ли мы еще улучшить?

Answer 1

Если массивы отсортированы, вы можете сделать это за линейное время и постоянное хранение.

• Начните с двух указателей, один из которых указывает на наименьший элемент A, а другой - на самый большой элемент B.
• Рассчитать сумму указанных элементов.
• Если он меньше k, увеличить указатель на A, чтобы он указывал на следующий по величине элемент.
• Если он больше k, уменьшите указатель на B, чтобы он указывал на следующий наименьший элемент.
• Если это ровно k, вы нашли пару. Переместите один из указателей и продолжайте искать следующую пару.

Если массивы изначально не отсортированы, вы можете сначала отсортировать их, а затем использовать приведенный выше алгоритм. Существует несколько различных подходов к их сортировке, которые вы можете использовать в зависимости от ожидаемого типа данных:

• Сравнительная сортировка, например Mergesort или Timsort .
• Подсчет сортировки .
• Radix sort .

Сравнительная сортировка потребует в среднем O (n log n) времени. Последние два быстрее, чем O (n log (n)), но могут быть непрактичными, если диапазон возможных значений во входных массивах очень велик.

Answer 2

Если у вас есть ограничение на максимально возможное число (назовем его M), то у вас может быть решение в O (M + n).

Логический массив false и отметьте как true все значения для элемента A. Затем для каждого элемента b из B проверьте, помечен ли номер элемента K-b как true.

Вы можете улучшить его, если вы используете хеш-карту вместо большого массива. Но я бы не стал считать, что в такого рода вопросах хэш-карта является своего рода обманом.

В любом случае это даст вам O (n) для вставки, а затем O (n) для запроса, всего O (n).

РЕДАКТИРОВАТЬ:

Один случай, когда это может быть полезно.

• У вас есть несортированные векторы размером 10 ^ 6, поэтому их сортировка и сопоставление выполняются в O (n log n) с n = 10 ^ 6.
• Вам нужно выполнить эту операцию 10 ^ 6 раз (разные векторы), сложность O (n * n * log n).
• Максимальное значение составляет 10 ^ 9.

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

• "O (10 ^ 9)" для создания массива (также с той же сложностью пространства)
• O (n) при каждом запуске, поэтому O (n * n) для всего.

Вы используете больше места, но в этом случае вы увеличили скорость на коэффициент log (n) ~ = 20!

Answer 3

Я бы создал хеш-таблицу, содержащую элементы одного массива, а затем перебрал бы другой массив, просматривая k - a(n), сгенерировав выходной элемент, если поиск завершился успешно. Это будет использовать O (n) пространство и время.

В C # это может выглядеть так:

var bSet = new HashSet(B);
var results = from a in A
              let b = k - a
              where bSet.Contains(b)
              select new { a, b };

Answer 4

template< typename T >
std::vector< std::pair< T, T > >
find_pairs( 
    std::vector< T > const & a, std::vector< T > const & b, T const & k  ) {

    std::vector< std::pair< T, T > > matches;

    std::sort( a.begin(), a.end() );  // O( A * lg A )
    std::sort( b.begin(), b.end() );  // O( B * lg B )

    typename std::vector< T >::const_iterator acit = a.begin();
    typename std::vector< T >::const_reverse_iterator bcit = b.rbegin();

    for( ; acit != a.end(); /* inside */ ) {
        for( ; bcit != b.rend(); /* inside */ ) {

            const T sum = *acit + *bcit;

            if( sum == k ) {
                matches.push_back( std::pair< T, T >( *acit, *bcit ) );
                ++acit;
                ++bcit;
            }
            else if( sum < k ) {
                ++acit;
            }
            else {  // sum > k
                ++bcit;
            }
        }
    }  // O( A + B )
    return matches;
}

Answer 5

Я использовал C ++, и это, казалось, дало мне желаемый результат. Надеюсь, это то, что вы искали.

using namespace std;

using data=std::pair<int,int>;

void search_pairs(std::vector<int>& A, std::vector<int>& B, const int total, std::vector<data>& output){

  std::sort(A.begin(),A.end(),[](const int i,const int j)->bool{return (i<j);});
  std::sort(B.begin(),B.end(),[](const int a,const int b)->bool{return (a<b);});
  std::vector<int>* minV(nullptr);
  std::vector<int>* maxV(nullptr);
  if(A.size()>B.size()) {minV=&B;maxV=&A;}
  else {minV=&A;maxV=&B;}
  for(auto&& itr:(*minV) ){
    auto remain(total-itr);
    if (std::binary_search (maxV->begin(), maxV->end(), remain)){
      data d{itr,remain};
      if (minV==&B) std::swap(d.first,d.second);
      output.push_back(d);
    }
  }
  if (minV==&B) std::reverse(output.begin(),output.end());  
}

int main() {

    size_t nb(0);
    scanf("%lu",&nb);
    for (size_t i=0;i<nb;++i){
        size_t a,b(0);
        int total(0);
        scanf("%lu %lu %d",&a,&b,&total);
        std::vector<int> A,B;
        for (size_t i=0;i<a;++i){
            int aux;
            scanf("%d",&aux);
            A.push_back(aux);
        } 
        for (size_t i=0;i<b;++i){
            int aux;
            scanf("%d",&aux);
            B.push_back(aux);
        } 
        std::vector<data> output;
        search_pairs(A, B, total, output);
    auto itr=std::begin(output);
    if (itr==std::end(output)) printf("-1"); 
    while (itr!=std::end(output)){
      printf("%d %d",(*itr).first, (*itr).second);
      if (++itr!=std::end(output)) printf(", ");
    }
        printf("\n");
    }
    //code
    return 0;
}