Берилген жуптар массиви Андагы бардык Симметриялык түгөйлөрдү табыңыз  


Кыйынчылык деңгээли жеңил
Көп суралган Amazon 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 arr [i] [1].
    2. SecondValue мааниси нөл эмес экендигин жана secondValue мааниси firstValueге барабар экендигин текшериңиз
    3. Эгер чын болсо, анда secondValue жана firstValue баскычтарын басып чыгарыңыз.
    4. Башка Hashmap ичине биринчиValue жана secondValue койду.
  3. Процессти а-дан 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ди текшеребиз жана жалган шарт түзөт, андыктан ал экөөнү тең картага киргизет.

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

i = 1,

firstValue = arr [i] [0] // жуп 1-элемент

secondValue = arr [i] [1] // жуп 2-элемент

firstValue = 30, secondValue = 40

Эгер анын картада мааниси бар болсо, 30ди текшеребиз жана жалган шарт түзөт, андыктан ал экөөнү тең картага киргизет.

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

i = 2,

firstValue = arr [i] [0] // жуп 1-элемент

secondValue = arr [i] [1] // жуп 2-элемент

firstValue = 6, secondValue = 9

Эгер анын картада мааниси бар болсо, 6ди текшеребиз жана жалган шарт түзөт, андыктан ал экөөнү тең картага киргизет.

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)

Комплекстик анализ  

Убакыт татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. HashMap колдонулгандыктан, киргизүү / жок кылуу / издөө иштерин жүргүзө алабыз O (1) убакыт.

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Картада элементтер сакталгандыктан. Космостун татаалдыгы сызыктуу.

шилтемелер