Пронађите парове са задатом сумом тако да се елементи пара налазе у различитим редовима


Ниво тешкоће Средњи
Често питани у амазонка ДЕ Схав Дирецти ГреиОранге Заиста Пинтерест терадата
Ред Хасх матрица

Изјава о проблему

Проблем „Пронађи парове са датим збројем тако да су елементи пара у различитим редовима“ наводи да сте добили матрицу целих бројева и вредност која се назива „зброј“. Изјава о проблему тражи да се открију сви парови у матрици која сабира до задате вредности која се назива збир, а такође би оба броја требала бити из другог реда. (Оба броја не смеју бити из истог реда).

Пример

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.

Објашњење

Добијамо матрицу целих бројева. Морамо открити све парове у матрици тако да елемент сваког пара има збир једнак датој вредности. А такође постоји и дати услов, бројеви које одаберемо у пару треба да буду из другог реда у матрици. Ако наставимо да га решавамо наивним приступом. И пређите сваки ред у елементу онда би требало О (н4). Решићемо то помоћу хеширања или Мап / ХасхМап. Прогласићемо мапу. Почните обилазити матрицу и ставите елементе матрице у мапу као кључ. А индекс реда и колоне његовог матричног елемента као вредност.

Вредност индекса редова и ступаца можемо ставити у мапу методом маке_паир у Ц ++. Или ако користимо јаву, можемо једноставно створити класу и то су објекти класе и можемо је сачувати на мапи. Касније, ако будемо морали да добијемо ту вредност, користићемо тај објект класе да бисмо добили те вредности реда и колоне.

Следећа ствар коју ћемо радити је прелазак матрице. У угнежђену петљу покупићемо сваки елемент матрице и одузети га од дате вредности збира и сачувати променљиву која се назива преостали зброј и проверити да ли карта садржи ову вредност ако је тачно, а затим проверити тренутни елемент матрице и преостали зброј не би требало да припадају истом реду, ако сви услови постану тачни, одштампајте елементе пара и наставите даље кретање да бисте сазнали све парове. Такође смо добили вредности реда и колоне те мапе као облик објекта као што смо горе поменули у објашњењу.

Пронађите парове са задатом сумом тако да се елементи пара налазе у различитим редовима

код

Ц ++ код за проналажење парова са датом сумом тако да се елементи пара налазе у различитим редовима

#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),

Јава код за проналажење парова са задатом сумом тако да се елементи пара налазе у различитим редовима

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),

Анализа сложености

Сложеност времена

Прелазимо матрицу и пошто користимо ХасхМап, у могућности смо да то постигнемо На2где „Н“ је број елемената у матрици.

Сложеност простора

НА) где "Н" је број елемената у матрици.