Рубрики

Найти пары с заданной суммой, чтобы элементы пары находились в разных строках

Дана матрица различных значений и сумма. Задача состоит в том, чтобы найти все пары в данной сумме, сумма которых равна данной сумме. Каждый элемент пары должен быть из разных строк, т.е. пара не должна лежать в одном ряду.

Примеры:

Input : mat[4][4] = {{1, 3, 2, 4},
                     {5, 8, 7, 6},
                     {9, 10, 13, 11},
                     {12, 0, 14, 15}}
        sum = 11
Output: (1, 10), (3, 8), (2, 9), (4, 7), (11, 0)

Способ 1 (простой)
Простое решение этой проблемы состоит в том, чтобы один за другим брать каждый элемент всех строк и находить пару, начиная с ближайшего следующего ряда в матрице. Временная сложность для этого подхода будет O (n 4 ).

Способ 2 (использовать сортировку)

  • Сортировать все строки в порядке возрастания. Временная сложность для этой предварительной обработки будет O (n 2 logn).
  • Теперь мы выберем каждую строку одну за другой и найдем элемент пары в оставшихся строках после текущей строки.
  • Возьмите два итератора влево и вправо . левый итератор указывает на левый угол текущей i-й строки, а правый итератор указывает на правый угол следующей j-й строки, в которой мы собираемся найти элемент пары.
  • Если mat [i] [left] + mat [j] [right] <sum, то left ++ ie; двигаться в i-й строке в направлении правого угла, в противном случае вправо ++ т.е. двигаться в j-й строке в направлении левого угла.

C ++

// C ++ программа для поиска пары с заданной суммой такой, что
// каждый элемент пары находится в разных строках.
#include<bits/stdc++.h>

using namespace std;

  

const int MAX = 100;

  
// Функция поиска пары для заданной суммы в матрице
// mat [] [] -> данная матрица
// n -> порядок матрицы
// сумма -> заданная сумма, для которой нам нужно найти пару

void pairSum(int mat[][MAX], int n, int sum)

{

    // Сначала сортируем все строки в порядке возрастания

    for (int i=0; i<n; i++)

        sort(mat[i], mat[i]+n);

  

    // Выбираем i строку и находим пару для элемента в i

    // строка в j-й строке, сумма которой равна заданной сумме

    for (int i=0; i<n-1; i++)

    {

        for (int j=i+1; j<n; j++)

        {

            int left = 0, right = n-1;

            while (left<n && right>=0)

            {

                if ((mat[i][left] + mat[j][right]) == sum)

                {

                    cout << "(" << mat[i][left]

                         << ", "<< mat[j][right] << "), ";

                    left++;

                    right--;

                }

                else

                {

                    if ((mat[i][left] + mat[j][right]) < sum)

                        left++;

                    else

                        right--;

                }

            }

        }

    }

}

  
// Драйвер программы для запуска дела

int main()

{

    int n = 4, sum = 11;

    int mat[][MAX] = {{1, 3, 2, 4},

                      {5, 8, 7, 6},

                      {9, 10, 13, 11},

                      {12, 0, 14, 15}};

    pairSum(mat, n, sum);

    return 0;

}

Джава

// Java-программа для поиска пары с
// заданная сумма такая, что каждый элемент
// пары в разных строках.

import java.util.Arrays;

class GFG {

static final int MAX = 100;

  
// Функция поиска пары для заданной суммы в
// матрица mat [] [] -> данная матрица
// n -> порядок матрицы
// сумма -> заданная сумма, для которой нам нужно найти пару

static void pairSum(int mat[][], int n, int sum) {

      

    // Сначала сортируем все строки в порядке возрастания

    for (int i = 0; i < n; i++)

    Arrays.sort(mat[i]);

  

    // Выбираем i строку и находим пару для элемента в i

    // строка в j-й строке, сумма которой равна заданной сумме

    for (int i = 0; i < n - 1; i++) {

        for (int j = i + 1; j < n; j++) {

            int left = 0, right = n - 1;

            while (left < n && right >= 0) {

                if ((mat[i][left] + mat[j][right]) == sum) {

                System.out.print("(" + mat[i][left] + ", " +

                                     mat[j][right] + "), ");

                left++;

                right--;

                }

                else {

                    if ((mat[i][left] + mat[j][right]) < sum)

                        left++;

                    else

                        right--;

                }

            }

        }

    }

}

  
// Код драйвера

public static void main(String[] args) {

    int n = 4, sum = 11;

    int mat[]

        [] = {{1 324},

              {5 876},

              {9 , 10, 13, 11},

              {120, 14, 15}};

    pairSum(mat, n, sum);

}
}
// Этот код предоставлен Anant Agarwal.

Python 3

# Python 3 программа для поиска пары с
# заданная сумма такая, что каждый элемент
# пара находится в разных строках.

MAX = 100

  
# Функция найти пару для данного
# сумма в матрице mat [] [] -> заданная матрица
# n -> порядок матрицы
# сумма -> указанная сумма, для которой мы
# нужно найти пару

def pairSum(mat, n, sum):

  

    # Сначала отсортируйте все строки

    # в порядке возрастания

    for i in range(n):

        mat[i].sort()

  

    # Выберите i-ую строку и найдите пару для

    # элемент в i-й строке в j-й строке

    # сумма которых равна заданной сумме

    for i in range(n - 1):

        for j in range(i + 1, n):

            left = 0

            right = n - 1

            while (left < n and right >= 0):

                if ((mat[i][left] + mat[j][right]) == sum):

                    print( "(", mat[i][left], 

                           ", ", mat[j][right], "), "

                                            end = " ")

                    left += 1

                    right -= 1

                  

                else:

                    if ((mat[i][left] + 

                         mat[j][right]) < sum):

                        left += 1

                    else:

                        right -= 1

  
Код водителя

if __name__ == "__main__":

    n = 4

    sum = 11

    mat = [[1, 3, 2, 4],

           [5, 8, 7, 6],

           [9, 10, 13, 11],

           [12, 0, 14, 15]]

    pairSum(mat, n, sum)

  
# Этот код добавлен
# by ChitraNayal


Выход:

(1, 10), (3, 8), (2, 9), (4, 7), (11, 0)

Временная сложность: O (n 2 logn + n ^ 3)
Вспомогательное пространство: O (1)

Метод 3 ( хеширование )

  1. Создайте пустую хеш-таблицу и сохраните все элементы матрицы в хэш-ключе, а их расположение — в качестве значений.
  2. Снова пройдитесь по матрице, чтобы проверить для каждого элемента, существует ли его пара в хеш-таблице или нет. Если существует, то сравните номера строк. Если номера строк не совпадают, выведите пару.

CPP

// C ++ программа для поиска пар с заданной суммой таких
// два элемента пар из разных строк
#include<bits/stdc++.h>

using namespace std;

  

const int MAX = 100;

  
// Функция поиска пары для заданной суммы в матрице
// mat [] [] -> данная матрица
// n -> порядок матрицы
// сумма -> заданная сумма, для которой нам нужно найти пару

void pairSum(int mat[][MAX], int n, int sum)

{

    // Создать хеш и сохранить все элементы матрицы

    // в качестве ключей, а номера строк и столбцов в качестве значений

    unordered_map<int, pair<int, int> > hm;

    for (int i=0; i<n; i++)

        for (int j=0; j<n; j++)

            hm[mat[i][j]] = make_pair(i, j);

  

    // Переходим матрицу снова, чтобы проверить каждый

    // элемент, существует ли его пара или нет.

    for (int i=0; i<n; i++)

    {

        for (int j=0; j<n; j++)

        {

            // ищем оставшуюся сумму в хэше

            int remSum = sum - mat[i][j];

            auto it = hm.find(remSum); // это итератор

                                       // типа unordered_map

  

            // Если существует элемент со значением, равным оставшейся сумме

            if (it != hm.end())

            {

                // Находим номера строк и столбцов элемента с

                // значение, равное оставшейся сумме.

                pair<int, int> p = it->second;

                int row = p.first, col = p.second;

  

                // Если номер строки пары не совпадает с текущим

                // строка, затем вывести ее как часть результата.

                // Второе условие, чтобы убедиться, что

                // пара печатается только один раз.

                if (row != i && row > i)

                   cout << "(" << mat[i][j] << ", "

                        << mat[row][col] << "), ";

            }

        }

    }

}

  
// Драйвер программы

int main()

{

    int n = 4, sum = 11;

    int mat[][MAX]= {{1, 3, 2, 4},

                     {5, 8, 7, 6},

                     {9, 10, 13, 11},

                     {12, 0, 14, 15}};

    pairSum(mat, n, sum);

    return 0;

}


Выход :

(1, 10), (3, 8), (2, 9), (4, 7), (11, 0), 

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

Сложность времени: O (n 2 ) в предположении, что операции вставки хеш-таблицы и поиска занимают O (1) времени.

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти пары с заданной суммой, чтобы элементы пары находились в разных строках

0.00 (0%) 0 votes