Дано масив пар Знайдіть у ньому всі симетричні пари


Рівень складності Легко
Часто запитують у Амазонка Capgemini Cisco FreeCharge Moonfrog Labs працювати Xome
масив Мішанина

Знайти всі симетричні пари - Вам дано кілька пар ан масив. Ви повинні з’ясувати в ній симетричні пари. Симетрична пара називається симетричною, коли в парах говорять (a, b) і (c, d), в яких 'b' дорівнює 'c', а 'a' дорівнює 'd', тобто (1 , 2) - симетрична пара (2, 1).

Приклад

Дано масив пар Знайдіть у ньому всі симетричні пари

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

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

  1. Заявіть a HashMap.
  2. У той час як i <n (довжина масиву)
    1. Установка firstValue до масиву [i] [0] та secondValue обробити [i] [1].
    2. Перевірте, чи не має значення secondValue значення null і чи значення secondValue дорівнює firstValue
    3. Якщо true, тоді надрукуйте secondValue і firstValue.
    4. В іншому випадку перше значення і друге значення вкладено в хеш-карту.
  3. Повторіть процес від a до d до циклу існує.

Пояснення

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

Використовуючи хеш-карту, ми спочатку зберігаємо перший елемент пари в firstValue і другий елемент пари для secondValue, ми можемо використовувати обидва елементи пари як ключ і значення. Ми будемо шукати його на карті, порівнюючи ключ однієї пари зі значенням іншої пари і значення тієї ж пари з ключем іншої пари.

Ми збираємося використовувати хеш-карту, давайте розглянемо приклад для заданого масиву пар, знайдіть у ній усі симетричні пари

Приклад

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

Ми будемо зберігати значення пар масиву у firstValue та secondValue, а потім перевірятимемо його.

i = 0,

firstValue = arr [i] [0] // пара 1-го елемента

secondValue = arr [i] [1] // пара 2-го елемента

firstValue = 1, secondValue = 2

Ми перевіримо, чи має значення 1 на карті і умова false, тож воно вкладає обидва значення на карту.

Карта = [{1: 2}]

i = 1,

firstValue = arr [i] [0] // пара 1-го елемента

secondValue = arr [i] [1] // пара 2-го елемента

firstValue = 30, secondValue = 40

Ми перевіримо, чи має значення 30 на карті і умова false, тож воно вкладає обидва значення на карту.

Карта = [{1: 2}, {30:40}]

i = 2,

firstValue = arr [i] [0] // пара 1-го елемента

secondValue = arr [i] [1] // пара 2-го елемента

firstValue = 6, secondValue = 9

Ми перевіримо, чи має значення 6 на карті і умова false, тож воно вкладає обидва значення на карту.

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

i = 3,

firstValue = arr [i] [0] // пара 1-го елемента

secondValue = arr [i] [1] // пара 2-го елемента

firstValue = 2, secondValue = 1

Ми перевіримо, чи має значення 1 на карті, і воно існує як '2', тоді ми перевіримо, якщо елемент secondValue дорівнює firstValue, і ця умова також відповідає.

Отже, ми друкуємо (1, 2)

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

i = 4,

firstValue = arr [i] [0] // пара 1-го елемента

secondValue = arr [i] [1] // пара 2-го елемента

firstValue = 9, secondValue = 6

Ми перевіримо наявність 6, чи має значення значення на карті, і воно існує як '9', тоді ми перевіримо, чи елемент secondValue дорівнює firstValue, і ця умова також відповідає.

Отже, ми друкуємо (1, 2), (6, 9)

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

код

Програма C ++ для пошуку всіх симетричних пар

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

Програма Java для пошуку всіх симетричних пар

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)

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

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

О (п) де "N" - кількість елементів у масиві. Оскільки ми використовували HashMap, ми можемо виконувати вставку / видалення / пошук у O (1) часу.

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

О (п) де "N" - кількість елементів у масиві. Оскільки ми зберегли елементи на карті. Складність простору лінійна.

посилання