Дат је низ парова. У њему пронађите све симетричне парове


Ниво тешкоће Лако
Често питани у амазонка Цапгемини Цисцо Бесплатно Моонфрог Лабс радити Ксоме
Ред Хасх

Пронађи све симетричне парове - Добија се неколико парова поредак. Морате открити симетричне парове у њему. За симетрични пар се каже да је симетричан када у паровима кажу (а, б) и (ц, д) у којима је „б“ једнако „ц“, а „а“ је једнако „д“, то јест (1 , 2) је симетрични пар (2, 1).

Пример

Дат је низ парова. У њему пронађите све симетричне парове

{{11, 20},{30,40},{4,5},{5,4},{40,30}}
(4, 5) (30, 40)

Алгоритам за проналажење свих симетричних парова

  1. Изјавите а ХасхМап.
  2. Док и <н (дужина низа)
    1. Сет фирстВалуе у низ [и] [0] и сецондВалуе да заокружи [и] [1].
    2. Проверите да ли вредност сецондВалуе није нулл и да ли је вредност сецондВалуе једнака фирстВалуе
    3. Ако је тачно, испишите сецондВалуе и фирстВалуе.
    4. Иначе су прву и другу вредност ставили у Хасхмап.
  3. Поновите поступак од а до д док петља не постоји.

Објашњење

Дали смо парове низова, унутар тог низа постоје неки симетрични парови. Изјава о проблему каже да морамо пронаћи све симетричне парове који постоје у низу. Једноставно можемо користити две петље и прећи оба низа један по један. Али то нас кошта више сложености времена и не можемо имати ефикасан код. Затим покушавамо да користимо бољи приступ да бисмо их прво сортирали у одређеном редоследу, али такође је потребна и наша ефикасност. Да бисмо добили ефикасан програм, морамо користити хеширање.

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

Користићемо хасхмапу, размотримо пример за дати низ парова, пронађите све симетричне парове у њему

Пример

arr={{1, 2},{30,40},{6,9},{2,1},{9,6}}

Чуваћемо вредност парова низа у фирстВалуе и сецондВалуе, а затим ћемо је проверавати.

и = 0,

фирстВалуе = арр [и] [0] // упарити 1. елемент

сецондВалуе = арр [и] [1] // упаривање 2. елемента

фирстВалуе = 1, сецондВалуе = 2

Проверићемо да ли има вредност на мапи и стање фалсе, па је обе вредности ставило на мапу.

Мапа = [{1: 2}]

и = 1,

фирстВалуе = арр [и] [0] // упарити 1. елемент

сецондВалуе = арр [и] [1] // упаривање 2. елемента

фирстВалуе = 30, сецондВалуе = 40

Проверићемо да ли има вредност на мапи и стање фалсе, па је обе вредности ставило на мапу.

Мапа = [{1: 2}, {30:40}]

и = 2,

фирстВалуе = арр [и] [0] // упарити 1. елемент

сецондВалуе = арр [и] [1] // упаривање 2. елемента

фирстВалуе = 6, сецондВалуе = 9

Проверићемо да ли има вредност на мапи и стање фалсе, па је обе вредности ставило на мапу.

Map=[{1:2},{30:40},{6:9}]

и = 3,

фирстВалуе = арр [и] [0] // упарити 1. елемент

сецондВалуе = арр [и] [1] // упаривање 2. елемента

фирстВалуе = 2, сецондВалуе = 1

Проверићемо да ли 1 има вредност да ли постоји на мапи и да ли постоји као '2', а затим ћемо проверити да ли је елемент сецондВалуе једнак фирстВалуе и да ли овај услов такође испуњава.

Па штампамо (1, 2)

Map=[{1:2},{30:40},{6:9}]

и = 4,

фирстВалуе = арр [и] [0] // упарити 1. елемент

сецондВалуе = арр [и] [1] // упаривање 2. елемента

фирстВалуе = 9, сецондВалуе = 6

Проверићемо да ли 6 има вредност да ли постоји на мапи и да ли постоји као '9', затим ћемо проверити да ли је елемент сецондВалуе једнак фирстВалуе и да ли овај услов такође задовољава.

Дакле, исписујемо (1, 2), (6, 9)

Map=[{1:2},{30:40},{6:9}]

код

Програм Ц ++ за проналажење свих симетричних парова

#include<unordered_map>
#include<iostream>
using namespace std;
void getSymmetricPair(int arr[][2], int row)
{
    unordered_map<int, int> myMap;

    for (int i = 0; i < row; i++)
    {
        int firstValue = arr[i][0];
        int secondValue = arr[i][1];

        if (myMap.find(secondValue) != myMap.end() && myMap[secondValue] == firstValue)
        {
            cout << "(" << secondValue << ", " << firstValue << ")"<<" ";
        }
        else
        {
            myMap[firstValue] = secondValue;
        }
    }
}
int main()
{
    int arr[5][2]= {{11,20},{30,40},{4,5},{5,4},{40,30}};
    getSymmetricPair(arr, 5);
}
(4, 5) (30, 40)

Јава програм за проналажење свих симетричних парова

import java.util.HashMap;
class pairSymmetrics
{
    static void getSymmetricPair(int arr[][])
    {
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();

        for (int i = 0; i < arr.length; i++)
        {
            int firstValue = arr[i][0];
            int secondValue = arr[i][1];
            Integer val = hashmap.get(secondValue);

            if (val != null && val == firstValue)
            {
                System.out.print("(" + secondValue + ", " + firstValue + ")" + " ");
            }
            else
            {
                hashmap.put(firstValue, secondValue);
            }
        }
    }

    public static void main(String arg[])
    {
        int arr[][]= {{11,20},{30,40},{4,5},{5,4},{40,30}};
        getSymmetricPair(arr);

    }
}
(4, 5) (30, 40)

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

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

Он) где „Н“ је број елемената у низу. Пошто смо користили ХасхМап, можемо извршити уметање / брисање / претраживање у О (1) време.

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

Он) где „Н“ је број елемената у низу. Пошто смо елементе ускладиштили на мапи. Сложеност простора је линеарна.

Референце