Улічваючы масіў пар Знайдзіце ў ім усе сіметрычныя пары


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка 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. Абвясціце а HashMap.
  2. У той час як я <n (даўжыня масіва)
    1. Усталёўка firstValue у масіў [i] [0] і secondValue абгрунтаваць [i] [1].
    2. Праверце, ці не значэнне secondValue роўна нулю, і ці роўна значэнне secondValue firstValue
    3. Калі дакладна, то надрукуйце secondValue і firstValue.
    4. У астатнім першае значэнне і другое значэнне былі змешчаны ў 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, ці мае яно значэнне на карце і ўмовы ілжывыя, таму ён змяшчае абодва значэнні на карту.

Карта = [{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 першаму значэнню, і гэтая ўмова таксама адпавядае.

Такім чынам, мы друкуем (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) часу.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве. Так як мы захавалі элементы на карце. Складанасць касмічнай прасторы лінейная.

Спасылкі