Берілген жұптар массиві Ондағы барлық симметриялық жұптарды табыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Capgemini Cisco FreeCharge Moonfrog зертханалары опера Xome
Array Hash

Барлық симметриялы жұптарды табыңыз - Сізге бірнеше жұптар беріледі массив. Ондағы симметриялық жұптарды табу керек. Симметриялы жұп «а», «с» -ге, ал «а» «d» -ге тең болатын (а, b) және (с, г) жұптары айтылғанда, симметриялы деп аталады, яғни (1 , 2) (2, 1) симметриялы жұбы.

мысал

Берілген жұптар массиві Ондағы барлық симметриялық жұптарды табыңыз

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

Барлық симметриялық жұптарды табу алгоритмі

  1. Декларация а HashMap.
  2. уақыт i <n (массивтің ұзындығы)
    1. жиынтық біріншіМән массивке [i] [0] және екіншіМән arr [i] [1] дейін.
    2. SecondValue мәні нөл емес екенін және secondValue мәні firstValue мәніне тең екендігін тексеріңіз
    3. Егер шын болса, онда secondValue және firstValue мәндерін басып шығарыңыз.
    4. Басқасы Hashmap ішіне бірінші мән мен екінші мәнді қойды.
  3. Процесті a-дан d-ге дейін цикл болғанға дейін қайталаңыз.

Түсіндіру

Біз массив жұбын бердік, сол массив ішінде бірнеше симметриялы жұптар бар. Есептер жиынтығында бар барлық симметриялық жұптарды табуымыз керек дейді. Біз жай ғана екі циклды қолданып, екі массивті де кезек-кезек айналып өтуімізге болады. Бірақ бұл бізге көп уақытты қажет етеді және бізде тиімді код болмайды. Одан кейін оларды белгілі бір ретпен сұрыптау үшін жақсы тәсілді қолдануға тырысамыз, бірақ бұл біздің тиімділігімізді қажет етеді. Сондықтан тиімді бағдарламаны алу үшін біз хэштеуді қолдануымыз керек.

Хэшмапты қолдану арқылы біз алдымен жұптың бірінші элементін сақтаймыз біріншіМән және жұптың екінші элементі екіншіМән, біз жұптың екі элементін де кілт және мән ретінде қолдана аламыз. Біз оны картадан бір жұптың кілтін екінші жұптың мәнімен және сол жұптың мәнімен екінші жұптың кілтімен салыстыру арқылы іздейміз.

Хэшмапты қолданамыз, берілген жұптар массивін қарастырайық, оның ішіндегі барлық симметриялы жұптарды табыңыз

мысал

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 мәнін тексереміз, егер екінші мәннің элементі бірінші мәнге тең болса және бұл шарт қанағаттандырылса, оны тексереміз.

Сонымен, біз басып шығарамыз (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 мәнін тексереміз, сонда біз екінші мән мәнінің мәні бірінші мәнге тең екендігін және бұл шарт қанағаттандыратынын тексереміз.

Сонымен (1, 2), (6, 9) басып шығарамыз

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

код

С ++ барлық симметриялы жұптарды табуға арналған бағдарлама

#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» - массивтегі элементтер саны. Біз картада элементтерді сақтағандықтан. Кеңістіктің күрделілігі сызықтық болып табылады.

Әдебиеттер тізімі