Найдите k пар с наименьшими суммами в двух массивах | Комплект 2

Опубликовано: 16 Января, 2022

Даны два массива arr1 [] и arr2 [], отсортированных в порядке возрастания, и целое число K. Задача состоит в том, чтобы найти k пар с наименьшими суммами таких, что один элемент пары принадлежит arr1 [], а другой элемент принадлежит arr2 [] . Размеры массивов могут быть разными. Предположим, что все элементы в каждом массиве различны.
Примеры:

 Ввод: a1 [] = {1, 7, 11}
       a2 [] = {2, 4, 6}
       k = 3
Вывод: [1, 2], [1, 4], [1, 6]
Возвращаются первые 3 пары 
из последовательности [1, 2], [1, 4], [1, 6], [7, 2],
[7, 4], [11, 2], [7, 6], [11, 4], [11, 6].

Ввод: a1 [] = {2, 3, 4}
       a2 [] = {1, 6, 5, 8}  
       к = 4
Вывод: [1, 2] [1, 3] [1, 4] [2, 6]
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Здесь обсуждался подход с временной сложностью O (k * n1).
Эффективный подход: поскольку массив уже отсортирован. Приведенный ниже алгоритм может быть использован для решения этой проблемы:

  • Идея состоит в том, чтобы поддерживать два указателя, один из которых указывает на одну пару в (a1, a2), а другой - на (a2, a1). Каждый раз сравнивайте суммы элементов, указанных двумя парами, и выведите минимальную. После этого увеличьте указатель на элемент в напечатанной паре, который был больше другого. Это помогает получить следующую возможную k наименьшую пару.
  • После того, как указатель был обновлен до элемента, так что он снова начинает указывать на первый элемент массива, обновите другой указатель до следующего значения. Это обновление выполняется циклически.
  • Кроме того, когда обе пары указывают на один и тот же элемент, обновите указатели в обеих парах, чтобы избежать печати дополнительной пары. Обновите указатель одной пары в соответствии с правилом 1, а другой - противоположным правилу 1. Это сделано для того, чтобы гарантировать, что все перестановки учтены и не будет повторений пар.

Ниже представлена работа алгоритма на примере 1:

a1[] = {1, 7, 11}, a2[] = {2, 4}, k = 3
Let the pairs of pointers be _one, _two
_one.first points to 1, _one.second points to 2 ; 
_two.first points to 2, _two.second points to 1
1st pair: 
Since _one and _two are pointing to same elements, print the pair once and update 
 

  • print [1, 2]

then update _one.first to 1, _one.second to 4 (following rule 1) ; 
_two.first points to 2, _two.second points to 7 (opposite to rule 1). 
If rule 1 was followed for both, then both of them would have been pointing to 1 and 4, 
and it is not possible to get all possible permutations.
2nd pair: 
Since a1[_one.first] + a2[_one.second] < a1[_two.second] + a2[_two.first], print them and update 
 

  • print [1, 4]

then update _one.first to 1, _one.second to 2 
Since _one.second came to the first element of the array once again, 
therefore _one.first points to 7
Repeat the above process for remaining K pairs

Below is the C++ implementation of the above approach: 
 

C++

// C++ program to print the k smallest
// pairs | Set 2
#include <bits/stdc++.h>
using namespace std;
 
typedef struct _pair {
    int first, second;
} _pair;
 
// Function to print the K smallest pairs
void printKPairs(int a1[], int a2[],
                 int size1, int size2, int k)
{
 
    // if k is greater than total pairs
    if (k > (size2 * size1)) {
        cout << "k pairs don"t exist ";
        return;
    }
 
    // _pair _one keeps track of
    // "first" in a1 and "second" in a2
    // in _two, _two.first keeps track of
    // element in the a2[] and _two.second in a1[]
    _pair _one, _two;
    _one.first = _one.second = _two.first = _two.second = 0;
 
    int cnt = 0;
 
    // Repeat the above process till
    // all K pairs are printed
    while (cnt < k) {
 
        // when both the pointers are pointing
        // to the same elements (point 3)
        if (_one.first == _two.second
            && _two.first == _one.second) {
            if (a1[_one.first] < a2[_one.second]) {
                cout << "[" << a1[_one.first]
                     << ", " << a2[_one.second] << "] ";
 
                // updates according to step 1
                _one.second = (_one.second + 1) % size2;
                if (_one.second == 0) // see point 2
                    _one.first = (_one.first + 1) % size1;
 
                // updates opposite to step 1
                _two.second = (_two.second + 1) % size2;
                if (_two.second == 0)
                    _two.first = (_two.first + 1) % size2;
            }
            else {
                cout << "[" << a2[_one.second]
                     << ", " << a1[_one.first] << "] ";
 
                // updates according to rule 1
                _one.first = (_one.first + 1) % size1;
                if (_one.first == 0) // see point 2
                    _one.second = (_one.second + 1) % size2;
 
                // updates opposite to rule 1
                _two.first = (_two.first + 1) % size2;
                if (_two.first == 0) // see point 2
                    _two.second = (_two.second + 1) % size1;
            }
        }
        // else update as necessary (point 1)
        else if (a1[_one.first] + a2[_one.second]
                 <= a2[_two.first] + a1[_two.second]) {
            if (a1[_one.first] < a2[_one.second]) {
                cout << "[" << a1[_one.first] << ", "
                     << a2[_one.second] << "] ";
 
                // updating according to rule 1
                _one.second = ((_one.second + 1) % size2);
                if (_one.second == 0) // see point 2
                    _one.first = (_one.first + 1) % size1;
            }
            else {
                cout << "[" << a2[_one.second] << ", "
                     << a1[_one.first] << "] ";
 
                // updating according to rule 1
                _one.first = ((_one.first + 1) % size1);
                if (_one.first == 0) // see point 2
                    _one.second = (_one.second + 1) % size2;
            }
        }
        else if (a1[_one.first] + a2[_one.second]
                 > a2[_two.first] + a1[_two.second]) {
            if (a2[_two.first] < a1[_two.second]) {
                cout << "[" << a2[_two.first] << ", " << a1[_two.second] << "] ";
 
                // updating according to rule 1
                _two.first = ((_two.first + 1) % size2);
                if (_two.first == 0) // see point 2
                    _two.second = (_two.second + 1) % size1;
            }
            else {
                cout << "[" << a1[_two.second]
                     << ", " << a2[_two.first] << "] ";
 
                // updating according to rule 1
                _two.second = ((_two.second + 1) % size1);
                if (_two.second == 0) // see point 2
                    _two.first = (_two.first + 1) % size1;
            }
        }
        cnt++;
    }
}
 
// Driver Code
int main()
{
 
    int a1[] = { 2, 3, 4 };
    int a2[] = { 1, 6, 5, 8 };
    int size1 = sizeof(a1) / sizeof(a1[0]);
    int size2 = sizeof(a2) / sizeof(a2[0]);
    int k = 4;
    printKPairs(a1, a2, size1, size2, k);
    return 0;
}

Java

// Java program to print
// the k smallest pairs
// | Set 2
import java.util.*;
class GFG{
 
static class _pair
{
  int first, second;
};
 
// Function to print the K
// smallest pairs
static void printKPairs(int a1[], int a2[],
                        int size1, int size2,
                        int k)
{
  // if k is greater than
  // total pairs
  if (k > (size2 * size1))
  {
    System.out.print("k pairs don"t exist ");
    return;
  }
 
  // _pair _one keeps track of
  // "first" in a1 and "second" in a2
  // in _two, _two.first keeps track of
  // element in the a2[] and _two.second
  // in a1[]
  _pair _one = new _pair();
  _pair  _two = new _pair();
  _one.first = _one.second =
  _two.first = _two.second = 0;
 
  int cnt = 0;
 
  // Repeat the above process
  // till all K pairs are printed
  while (cnt < k)
  {
    // when both the pointers are
    // pointing to the same elements
    // (point 3)
    if (_one.first == _two.second &&
        _two.first == _one.second)
    {
      if (a1[_one.first] <
          a2[_one.second])
      {
        System.out.print("[" +  a1[_one.first] +
                         ", " +  a2[_one.second] +
                         "] ");
 
        // updates according to step 1
        _one.second = (_one.second + 1) %
                       size2;
         
        // see point 2
        if (_one.second == 0)
          _one.first = (_one.first + 1) %
                        size1;
 
        // updates opposite to step 1
        _two.second = (_two.second + 1) %
                       size2;
         
        if (_two.second == 0)
          _two.first = (_two.first + 1) %
                        size2;
      }
      else
      {
        System.out.print("[" +  a2[_one.second] +
                         ", " +  a1[_one.first] +
                         "] ");
 
        // updates according to rule 1
        _one.first = (_one.first + 1) %
                      size1;
         
        // see point 2
        if (_one.first == 0)
          _one.second = (_one.second + 1) %
                         size2;
 
        // updates opposite to rule 1
        _two.first = (_two.first + 1) %
                      size2;
         
        // see point 2
        if (_two.first == 0)
           
          _two.second = (_two.second + 1) %
                         size1;
      }
    }
     
    // else update as
    // necessary (point 1)
    else if (a1[_one.first] +
             a2[_one.second] <=
             a2[_two.first] +
             a1[_two.second])
    {
      if (a1[_one.first] <
          a2[_one.second])
      {
        System.out.print("[" +  a1[_one.first] +
                         ", " + a2[_one.second] +
                         "] ");
 
        // updating according to rule 1
        _one.second = ((_one.second + 1) %
                        size2);
         
        // see point 2
        if (_one.second == 0)
          _one.first = (_one.first + 1) %
                        size1;
      }
      else
      {
        System.out.print("[" +  a2[_one.second] +
                         ", " + a1[_one.first] +
                         "] ");
 
        // updating according to rule 1
        _one.first = ((_one.first + 1) %
                       size1);
         
        // see point 2
        if (_one.first == 0)
          _one.second = (_one.second + 1) %
                         size2;
      }
    }
    else if (a1[_one.first] +
             a2[_one.second] >
             a2[_two.first] +
             a1[_two.second])
    {
      if (a2[_two.first] <
          a1[_two.second])
      {
        System.out.print("[" +  a2[_two.first] +
                         ", " +  a1[_two.second] +
                         "] ");
 
        // updating according to rule 1
        _two.first = ((_two.first + 1) %
                       size2);
         
        // see point 2
        if (_two.first == 0)
          _two.second = (_two.second + 1) %
                         size1;
      }
      else {
        System.out.print("[" +  a1[_two.second] +
                         ", " +  a2[_two.first] +
                         "] ");
 
        // updating according to rule 1
        _two.second = ((_two.second + 1) %
                        size1);
         
        // see point 2
        if (_two.second == 0)
          _two.first = (_two.first + 1) %
                        size1;
      }
    }
    cnt++;
  }
}
 
// Driver Code
public static void main(String[] args)
{
  int a1[] = {2, 3, 4};
  int a2[] = {1, 6, 5, 8};
  int size1 = a1.length;
  int size2 = a2.length;
  int k = 4;
  printKPairs(a1, a2,
              size1, size2, k);
}
}
 
// This code is contributed by gauravrajput1

Python3

# Pyth
Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022