Знайдіть пари з заданою сумою, щоб елементи пари знаходились у різних рядках


Рівень складності Medium
Часто запитують у Амазонка Д. Е. Шоу Directi GreyOrange Дійсно Пінтерест Терадата
масив Мішанина Матриця

Постановка проблеми

"Знайти пари з заданою сумою так, щоб елементи пари знаходились у різних рядках", говорить про те, що вам дають матрицю цілих чисел і значення, яке називається "сума". Постановка задачі вимагає з'ясувати всі пари в матриці, яка підсумовує до заданого значення, яке називається сумою, а також обидва числа повинні бути з іншого рядка. (Обидва числа не повинні бути з одного рядка).

Приклад

int matrix[][]= {{3, 4, 7, 2},

{8, 9, 1, 10},

{5, 4, 0, 4},

{12, 0, 1, 13}};



sum = 15
(3, 12), (7, 8), (2, 13), (10, 5)

Пояснення: Кожне з чисел кожної пари з іншого рядка.

Алгоритм пошуку пар із заданою сумою таким, що елементи пари знаходяться в різних рядках

1. Declare a map.
2. Put all the values of the matrix into the map with their row and column index.
3. Traverse the matrix.
  1. Set the remainingValue to the difference of sum and each value of the matrix.
  2. Check if the map contains the value of remainingValue if true then get its row and column index which we already put it into the map.
    1. Check if this row value is not equal to current i and also a row is greater than i.
      1. If true then print the matrix[i][j] and matrix[row][column].
4. Keep repeating the process until the whole matrix is traversed.

Пояснення

Нам дана матриця цілих чисел. Ми маємо виявити всі пари в матриці, щоб елемент кожної пари мав суму, рівну заданому значенню. А також є така умова, що числа, які ми обираємо в парі, повинні бути з іншого рядка матриці. Якщо ми продовжимо вирішувати це з наївним підходом. І перебіг кожного рядка в елементі, тоді це займе O (n4). Ми вирішимо це за допомогою хешування або Карта / HashMap. Ми будемо оголошувати карту. Почніть обхід матриці та помістіть елементи матриці на карту як ключ. І індекс рядка та стовпця його матричного елемента як значення.

Ми можемо помістити значення індексу рядків і стовпців на карту, використовуючи метод make_pair у C ++. Або якщо ми використовуємо java, ми можемо просто створити клас, і це об’єкти класу, ми можемо зберігати його на карті. Пізніше, якщо нам доведеться отримати це значення, ми будемо використовувати цей об'єкт класу, щоб отримати ці значення рядків і стовпців.

Наступне, що ми будемо робити, це обхід матриці. У вкладеному циклі ми підберемо кожен елемент матриці і віднімемо його від заданого значення суми та збережемо змінну, що називається не повинні належати до одного рядка, якщо всі умови стають істинними, тоді надрукуйте елементи пари і продовжуйте подальший обхід, щоб з'ясувати всі пари. Ми також отримали значення рядків і стовпців цієї карти як форму об’єкта, як ми згадали вище в поясненні.

Знайдіть пари з заданою сумою, щоб елементи пари знаходились у різних рядках

код

Код С ++ для пошуку пар із заданою сумою, щоб елементи пари знаходились у різних рядках

#include<iostream>
#include<unordered_map>

using namespace std;

const int MAX = 100;

void makePairWithGivenSum (int matrix[][MAX], int n, int sum)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            MAP[matrix[i][j]] = make_pair(i, j);

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            int remainingSum = sum - matrix[i][j];
            auto it = MAP.find(remainingSum);

            if (it != MAP.end())
            {
                pair<int, int> p = it->second;
                int row = p.first, col = p.second;
                if (row != i && row > i)
                    cout << "(" << matrix[i][j] << ", "
                         << matrix[row][col] << "), ";
            }
        }
    }
}
int main()
{
    int n = 4, sum = 11;
    int matrix[][MAX]= {{3, 4, 7, 2},
        {8, 9, 1, 10},
        {5, 4, 0, 4},
        {12, 0, 1, 13}
    };
    makePairWithGivenSum (matrix, n, sum);
    return 0;
}
(3, 8), (7, 4), (2, 9), (10, 1),

Код Java для пошуку пар із заданою сумою, щоб елементи пари знаходились у різних рядках

import java.util.HashMap;
class Pair
{
    int first, second;
    Pair(int first, int second)
    {
        this.first=first;
        this.second=second;
    }
}
class pairSum
{
    public static void makePairWithGivenSum(int matrix[][], int n, int sum)
    {
        HashMap<Integer, Pair > MAP=new HashMap<Integer, Pair>();
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                MAP.put(matrix[i][j], new Pair(i,j));
            }
        }
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                int remainingSum = sum - matrix[i][j];

                if (MAP.containsKey(remainingSum))
                {
                    Pair p = MAP.get(remainingSum);
                    int row = p.first, col = p.second;
                    if (row != i && row > i)
                        System.out.print("(" + matrix[i][j] + ", " + matrix[row][col] + "), ");

                }
            }
        }
    }
    public static void main(String [] args)
    {
        int n = 4, sum = 15;
        int matrix[][]= {{3, 4, 7, 2},
            {8, 9, 1, 10},
            {5, 4, 0, 4},
            {12, 0, 1, 13}
        };
        makePairWithGivenSum (matrix, n, sum);
    }
}
(3, 12), (7, 8), (2, 13), (10, 5),

Аналіз складності

Складність часу

Ми обходимо матрицю, і оскільки ми використовуємо HashMap, ми можемо досягти О (н.)2де "N" - кількість елементів у матриці.

Складність простору

O (N) де "N" - кількість елементів у матриці.