جوڑیوں کی ایک صف دیئے جانے پر اس میں سارے توازن کے جوڑے تلاش کریں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون Capgemini سسکو فریچارج مونفروگ لیبز اوپرا زوم
لڑی ہیش

تمام سڈولک جوڑے تلاش کریں۔ آپ کو کچھ جوڑے دئے جاتے ہیں صف. آپ کو اس میں توازن کے جوڑے تلاش کرنا ہوں گے۔ توازن کی جوڑی کو متوازی کہا جاتا ہے جب جوڑے میں کہتے ہیں کہ (الف ، بی) اور (سی ، ڈی) جس میں 'بی' 'سی' کے برابر ہے اور 'اے' 'ڈی' کے برابر ہے ، یعنی ، (1) ، 2) (2 ، 1) کی ہم آہنگی کی جوڑی ہے۔

مثال کے طور پر

جوڑیوں کی ایک صف دیئے جانے پر اس میں سارے توازن کے جوڑے تلاش کریں

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

تمام توازن کے جوڑے تلاش کرنے کے لئے الگورتھم

  1. اعلان a ہش میپ.
  2. جبکہ i <n (صف کی لمبائی)
    1. سیٹ کریں فرسٹ ویلیو کرنے کے لئے [i] [0] اور دوسرا قیمت to arr [i] [1]۔
    2. چیک کریں کہ آیا سیکنڈ ویلیو کی قیمت کالعدم نہیں ہے اور اگر سیکنڈ ویلیو کی قیمت پہلی قیمت کے برابر ہے
    3. اگر سچ ہے تو ، پھر سیکنڈ ویلیو اور فرسٹ ویلیو پرنٹ کریں۔
    4. دوسری نے ہسٹمپ میں پہلا ویلیو اور دوسرا والیو ڈال دیا۔
  3. اس عمل کو ایک سے لے کر ڈی تک دہرائیں جب تک لوپ موجود نہیں ہے۔

وضاحت

ہم نے ایک سرنی جوڑے دیئے ہیں ، اس صف کے اندر کچھ ہم آہنگی جوڑے موجود ہیں۔ مسئلے کے بیان میں کہا گیا ہے کہ ہمیں وہ ساری سمترا جوڑے تلاش کرنا ہوں گے جو ایک صف میں موجود ہوں۔ ہم آسانی سے دو لوپ استعمال کرسکتے ہیں اور ایک دوسرے کے بعد دونوں ارایوں کو عبور کرسکتے ہیں۔ لیکن اس میں ہمارے لئے زیادہ وقت کی پیچیدگی کا سامنا کرنا پڑتا ہے اور ہمارے پاس موثر کوڈ نہیں ہوسکتا ہے۔ پھر ہم کوشش کرتے ہیں کہ ان کو پہلے سے مخصوص ترتیب میں ترتیب دینے کے ل a بہتر نقطہ نظر کو استعمال کیا جائے لیکن اس میں ہماری کارکردگی بھی لی جاتی ہے۔ لہذا ایک موثر پروگرام حاصل کرنے کے ل we ہمیں ہیشنگ کا استعمال کرنا چاہئے۔

ایک ہیش میپ کا استعمال کرکے ، ہم پہلے جوڑا کا پہلا عنصر اسٹور کرتے ہیں فرسٹ ویلیو اور جوڑی کا دوسرا عنصر دوسرا قیمت، ہم ایک جوڑے کے دونوں عناصر کو ایک کلید اور قدر کے بطور استعمال کرسکتے ہیں۔ ہم ایک جوڑے کی ایک چابی کا ایک اور جوڑی کی قیمت اور اسی جوڑی کی قدر کو دوسرے جوڑے کی کنجی سے موازنہ کرکے اس کا نقشہ تلاش کریں گے۔

ہم ایک ہیشیمپ استعمال کرنے جارہے ہیں آئیے ، ایک جوڑا بنانے کے ل for ایک مثال پر غور کریں ، اس میں تمام ہم آہنگی جوڑے ڈھونڈیں۔

مثال کے طور پر

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

ہم صف کی صف کی جوڑی کی قیمت کو پہلے والے اور دوسرے نمبر میں محفوظ کریں گے اور پھر ہم اس کی جانچ پڑتال کریں گے۔

i = 0،

فرسٹ ویلیو = ارار [i] [0] // جوڑی اول عنصر

سیکنڈویلو = ارار [i] [1] // جوڑی دوسرا عنصر

فرسٹ ویلیو = 1 ، سیکنڈ ویلیو = 2

ہم 1 کو چیک کریں گے کہ اگر اس کی نقشہ میں کوئی قیمت ہے اور شرط غلط ہے تو اس نے نقشہ میں دونوں کی قیمت ڈال دی۔

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

i = 1،

فرسٹ ویلیو = ارار [i] [0] // جوڑی اول عنصر

سیکنڈویلو = ارار [i] [1] // جوڑی دوسرا عنصر

فرسٹ ویلیو = 30 ، سیکنڈ ویلیو = 40

ہم 30 کو چیک کریں گے کہ اگر اس کی نقشہ میں کوئی قیمت ہے اور شرط غلط ہے تو اس نے نقشہ میں دونوں کی قیمت ڈال دی۔

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

i = 2،

فرسٹ ویلیو = ارار [i] [0] // جوڑی اول عنصر

سیکنڈویلو = ارار [i] [1] // جوڑی دوسرا عنصر

فرسٹ ویلیو = 6 ، سیکنڈ ویلیو = 9

ہم 6 کو چیک کریں گے کہ اگر اس کی نقشہ میں کوئی قیمت ہے اور شرط غلط ہے تو اس نے نقشہ میں دونوں کی قیمت ڈال دی۔

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

i = 3،

فرسٹ ویلیو = ارار [i] [0] // جوڑی اول عنصر

سیکنڈویلو = ارار [i] [1] // جوڑی دوسرا عنصر

فرسٹ ویلیو = 2 ، سیکنڈ ویلیو = 1

ہم 1 کو چیک کریں گے کہ اگر اس کی نقشہ کسی قدر میں موجود ہے اور یہ '2' کی طرح موجود ہے تو ہم چیک کریں گے کہ ، اگر سیکنڈویلو کا عنصر فرسٹ ویلیو کے برابر ہے اور یہ شرط بھی پوری ہوجاتی ہے۔

تو ہم پرنٹ کرتے ہیں (1 ، 2)

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

i = 4،

فرسٹ ویلیو = ارار [i] [0] // جوڑی اول عنصر

سیکنڈویلو = ارار [i] [1] // جوڑی دوسرا عنصر

فرسٹ ویلیو = 9 ، سیکنڈ ویلیو = 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)

جاوا پروگرام تمام ہم آہنگی کے جوڑے تلاش کرنے کے لئے

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 (1) وقت.

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ چونکہ ہم نے نقشے میں عناصر کو ذخیرہ کرلیا ہے۔ خلائی پیچیدگی لکیری ہے۔

حوالہ جات