Даден масив от двойки Намерете всички симетрични двойки в него  


Ниво на трудност Лесно
Често задавани в Амазонка Capgemini Cisco FreeCharge Moonfrog Labs опера Xome
Array Хашиш

Намерете всички симетрични двойки - получавате няколко двойки масив. Трябва да откриете симетричните двойки в него. Казва се, че симетричната двойка е симетрична, когато по двойки казват (a, b) и (c, d), в които „b“ е равно на „c“ и „a“ е равно на „d“, т.е. , 1) е симетрична двойка от (2, 2).

Пример  

Даден масив от двойки Намерете всички симетрични двойки в негощифт

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

Алгоритъм за намиране на всички симетрични двойки  

  1. Декларирайте а HashMap.
  2. Докато i <n (дължина на масива)
    1. комплект firstValue до масив [i] [0] и secondValue да се получи [i] [1].
    2. Проверете дали стойността на secondValue не е нула и дали стойността на secondValue е равна на firstValue
    3. Ако е вярно, тогава отпечатайте secondValue и firstValue.
    4. В противен случай поставете firstValue и secondValue в Hashmap.
  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)

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

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

О (п) където "н" е броят на елементите в масива. Тъй като използвахме HashMap, можем да извършим вмъкване / изтриване / търсене в O (1) време.

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

О (п) където "н" е броят на елементите в масива. Тъй като сме съхранили елементи в картата. Сложността на пространството е линейна.

Препратки