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

Ответ 1

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

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

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

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

EDIT:

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

• У вас есть неупорядоченные векторы размером 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!

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

Ответ 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;
}

Ответ 5

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

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;
}