با توجه به آرایه ای از جفت ها ، همه جفت های متقارن را در آن پیدا کنید


سطح دشواری ساده
اغلب در آمازون Capgemini سیسکو شارژ رایگان آزمایشگاه Moonfrog اپرا Xome
صف مخلوط

همه جفت های متقارن را پیدا کنید - به شما چند جفت an داده می شود صف. شما باید جفت های متقارن موجود در آن را پیدا کنید. جفت متقارن وقتی متقارن باشد گفته می شود که در جفت می گویند (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 به arr [i] [1]
    2. بررسی کنید که آیا ارزش secondValue خالی نیست و آیا مقدار secondValue برابر با firstValue است
    3. اگر درست است ، secondValue و firstValue را چاپ کنید.
    4. Else اولینValue و secondValue را در Hashmap قرار دهید.
  3. فرآیند را از حلقه a تا d تکرار کنید.

توضیح

ما یک جفت آرایه داده ایم ، در داخل آن آرایه برخی از جفت های متقارن وجود دارد. عبارت مسئله می گوید که ما باید تمام جفت های متقارن موجود در یک آرایه را پیدا کنیم. به راحتی می توانیم از دو حلقه استفاده کنیم و هر دو آرایه را یکی یکی رد کنیم. اما این هزینه برای ما پیچیدگی زمان بیشتری است و ما نمی توانیم یک کد کارآمد داشته باشیم. سپس سعی می کنیم از روش بهتری برای مرتب سازی آنها ابتدا به ترتیب خاص استفاده کنیم اما همچنین کارایی ما را می گیرد. بنابراین برای دستیابی به یک برنامه کارآمد باید از هش کردن استفاده کنیم.

با استفاده از hashmap ، ما اولین عنصر جفت را ذخیره می کنیم firstValue و عنصر دوم جفت به secondValue، می توانیم از هر دو عنصر یک جفت به عنوان یک کلید و یک مقدار استفاده کنیم. ما با مقایسه کلید یک جفت با مقدار یک جفت دیگر و مقدار همان جفت با کلید جفت دیگر ، آن را در نقشه جستجو خواهیم کرد.

ما قصد داریم از یک هشماپ استفاده کنیم اجازه دهید مثالی را برای آرایه ای از جفت ها در نظر بگیریم ، همه جفت های متقارن را در آن پیدا کنیم

مثال

arr={{1, 2},{30,40},{6,9},{2,1},{9,6}}

مقدار جفت های آرایه را در firstValue و secondValue ذخیره خواهیم کرد و سپس آن را بررسی خواهیم کرد.

من = 0 ،

firstValue = arr [i] [0] // جفت عنصر 1

secondValue = arr [i] [1] // جفت عنصر 2

firstValue = 1 ، secondValue = 2

اگر مقدار آن در نقشه و شرط نادرست باشد ، 1 را بررسی خواهیم کرد ، بنابراین هر دو مقدار را در نقشه قرار می دهد.

نقشه = [{1: 2}]

من = 1 ،

firstValue = arr [i] [0] // جفت عنصر 1

secondValue = arr [i] [1] // جفت عنصر 2

firstValue = 30 ، secondValue = 40

اگر مقدار آن در نقشه و شرط نادرست باشد ، 30 را بررسی خواهیم کرد ، بنابراین هر دو مقدار را در نقشه قرار می دهد.

نقشه = [{1: 2} ، {30:40}]

من = 2 ،

firstValue = arr [i] [0] // جفت عنصر 1

secondValue = arr [i] [1] // جفت عنصر 2

firstValue = 6 ، secondValue = 9

اگر مقدار آن در نقشه و شرط نادرست باشد ، 6 را بررسی خواهیم کرد ، بنابراین هر دو مقدار را در نقشه قرار می دهد.

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

من = 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}]

من = 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)

برنامه جاوا برای یافتن همه جفت های متقارن

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" تعداد عناصر آرایه است. از آنجا که ما عناصر را در نقشه ذخیره کرده ایم. پیچیدگی فضا خطی است.

منابع