Як массиви ҷуфтҳо дода шудааст Дар он ҳамаи ҷуфтҳои симметрӣ пайдо кунед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Capgemini Cisco FreeCharge Озмоишгоҳҳои Moonfrog Опера Xome
тартиботи ҳарбӣ Хаш

Ҳама ҷуфтҳои симметриро ёбед - Ба шумо якчанд ҷуфти an дода мешавад асал. Шумо бояд ҷуфтҳои симметриро дар он пайдо кунед. Ҷуфти симметрӣ вақте номбар мешавад, ки ҷуфтҳо мегӯянд (а, б) ва (в, г), ки дар онҳо 'б' ба 'в' ва 'а' ба '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. маҷмӯи аввалАрзиш ба массиви [i] [0] ва Арзиши дуюм ба arr [i] [1].
    2. Санҷед, ки оё арзиши secondValue нул нест ва агар арзиши secondValue ба firstValue баробар бошад
    3. Агар рост бошад, пас secondValue ва firstValue -ро чоп кунед.
    4. Дигар арзиши аввал ва арзишро ба Hashmap гузошт.
  3. Равандро аз а то d то ҳалқаи мавҷуда такрор кунед.

Шарҳ

Мо ҷуфтҳои массивро додем, дар дохили он массив баъзе ҷуфтҳои симметрӣ мавҷуданд. Дар баёни масъала гуфта мешавад, ки мо бояд ҳамаи ҷуфтҳои симметрӣеро, ки дар массив мавҷуданд, пайдо кунем. Мо метавонем танҳо ду ҳалқа истифода барем ва ҳарду массивро як ба як гузарем. Аммо ин барои мо мураккабии бештарро талаб мекунад ва мо наметавонем рамзи муассир дошта бошем. Пас мо кӯшиш мекунем, ки муносибати беҳтарро барои ҷобаҷогузории онҳо аввал бо тартиби муайян истифода барем, аммо ин самаранокии моро талаб мекунад. Пас, барои ба даст овардани як барномаи муассир мо бояд ҳешингро истифода барем.

Бо истифода аз hashmap, мо аввал унсури якуми ҷуфтро барои нигоҳ медорем аввалАрзиш ва унсури дуюми ҷуфт ба Арзиши дуюм, мо метавонем ҳарду унсури ҷуфтро ҳамчун калид ва арзиш истифода барем. Мо онро дар харита бо муқоисаи калиди як ҷуфт бо арзиши ҷуфти дигар ва арзиши ҳамон ҷуфт бо калиди ҷуфти дигар ҷустуҷӯ хоҳем кард.

Мо hashmap -ро истифода мебарем, биёед як мисолро барои як қатор ҷуфтҳо дида бароем, дар он ҳамаи ҷуфтҳои симметрӣ пайдо кунед

мисол

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)

Таҳлили мураккабӣ

Мураккабии вақт

Эй (н) ки дар "Н" шумораи унсурҳои массив аст. Азбаски мо HashMap -ро истифода кардем, мо метавонем ворид / ҳазф / ҷустуҷӯро иҷро кунем О (1) вақт.

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст. Азбаски мо унсурҳоро дар харита нигоҳ доштаем. Мураккабии фазо хаттӣ аст.

Адабиёт