जोडीहरूको एर्रे दिइयो यसमा सबै सिमेट्रिक जोडीहरू फेला पार्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन Capgemini सिस्को फ्रीचार्ज मूनफ्रग ल्याबहरू ओपेरा Xome
एरे हैश

सबै सममित जोडीहरू फेला पार्नुहोस् - तपाईलाई केहि जोडी दिइन्छ array। तपाईंले यसमा सिमेट्रिक जोडीहरू पत्ता लगाउनु पर्छ। सममित जोडी सममेटिक भनिन्छ जब जोडीहरु (a, b) र (c, d) मा जसमा 'b' 'c' बराबर हुन्छ र 'a' d d बराबर हुन्छ, अर्थात, (१ , २) सममित जोडी हो (२, १)।

उदाहरणका

जोडीहरूको एर्रे दिइयो यसमा सबै सिमेट्रिक जोडीहरू फेला पार्नुहोस्

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

सबै सममित जोडीहरू फेला पार्न एल्गोरिथ्म

  1. घोषणा गर्नुहोस् हशम्याप.
  2. जबकि म <एन (एर्रेको लम्बाई)
    1. सेट firstValue एर्रेमा [i] [०] र दोस्रो एर गर्न [i] [१]।
    2. यदि दोस्रोValue को मान शून्य छैन जाँच गर्नुहोस् र यदि दोस्रोValue को मान firstValue बराबर छ भने।
    3. यदि सहि छ भने, त्यसपछि सेकेन्डभल्लू र फर्स्टभल्यु प्रिन्ट गर्नुहोस्।
    4. अन्यले पहिलोValue र दोस्रो भल्भलाई ह्यासम्यापमा राख्यो।
  3. लूप अवस्थित नभएसम्म एक देखि d सम्म प्रक्रिया दोहोर्याउनुहोस्।

स्पष्टीकरण

हामीले एर्रे जोडी दिएका छौं, त्यो एर्रे भित्र केहि सममेट्रिक जोडी अवस्थित छन्। समस्या कथन भन्छ कि हामीले ती सबै सममित जोडीहरू फेला पार्नु पर्छ जुन एर्रेमा अवस्थित छन्। हामी केवल दुई लूपहरू प्रयोग गर्न सक्छौं र दुबै एर्रेलाई एक एक गरी ट्र्यावर्स गर्न सक्छौं। तर यसले हामीलाई अधिक समय जटिलता खर्च गर्दछ र हामीसँग एक कुशल कोड हुन सक्दैन। हामी त्यसोभए राम्रो क्रम प्रयोग गर्ने प्रयास गर्छौं तिनीहरूलाई विशेष क्रममा क्रमबद्ध गर्नका लागि तर यसले हाम्रो दक्षता पनि लिन्छ। त्यसोभए एक कुशल कार्यक्रम प्राप्त गर्न हामीले ह्यासिंग प्रयोग गर्नु पर्छ।

एक ह्यासम्याप प्रयोग गरेर, हामी पहिले जोडीको पहिलो एलिमेन्टमा भण्डार गर्दछौं firstValue र जोडीको दोस्रो तत्वमा दोस्रो, हामी एक जोडी को दुबै दुबै कुञ्जी र मानको रूपमा प्रयोग गर्न सक्छौं। हामी यसको लागि अर्को जोडीको मानसँग अर्को जोडीको कुञ्जीसँग अर्को जोडीको मान र एउटा जोडीको कुञ्जी तुलना गरेर नक्सामा खोजी गर्नेछौं।

हामी एक ह्यासम्याप प्रयोग गर्न जाँदैछौं, जोडीको एरे दिईएकोमा उदाहरण विचार गरौं, यसमा सबै सिमेट्रिक जोडीहरू फेला पार्नुहोस्।

उदाहरणका

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

हामी एर्रेको जोडी मानलाई फर्स्टभल्याभ र सेकेन्डभल्यूमा भण्डार गर्नेछौं र त्यसपछि हामी यसलाई जाँच गर्नेछौं।

i = ०,

firstValue = एर [i] [०] // जोडी पहिलो तत्व

दोस्रोValue = arr [i] [1] // जोडी दोस्रो तत्व

firstValue = १, सेकेन्डभल्यु = २

हामी १ को लागि जाँच गर्नेछौं यदि यसको नक्सामा मूल्य छ र यो गलत छ भने यसले दुबै मानलाई नक्सामा राख्दछ।

नक्शा = [{१: २}]

i = ०,

firstValue = एर [i] [०] // जोडी पहिलो तत्व

दोस्रोValue = arr [i] [1] // जोडी दोस्रो तत्व

firstValue = १, सेकेन्डभल्यु = २

हामी १ को लागि जाँच गर्नेछौं यदि यसको नक्सामा मूल्य छ र यो गलत छ भने यसले दुबै मानलाई नक्सामा राख्दछ।

नक्सा = [{१: २}, :1 :2०::30०}]

i = ०,

firstValue = एर [i] [०] // जोडी पहिलो तत्व

दोस्रोValue = arr [i] [1] // जोडी दोस्रो तत्व

firstValue = १, सेकेन्डभल्यु = २

हामी १ को लागि जाँच गर्नेछौं यदि यसको नक्सामा मूल्य छ र यो गलत छ भने यसले दुबै मानलाई नक्सामा राख्दछ।

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

i = ०,

firstValue = एर [i] [०] // जोडी पहिलो तत्व

दोस्रोValue = arr [i] [1] // जोडी दोस्रो तत्व

firstValue = १, सेकेन्डभल्यु = २

हामी १ जाँच गर्नेछौं यदि यसको मानचित्रमा अवस्थित छ र यो '२' को रूपमा अवस्थित छ भने हामी जाँच गर्नेछौं यदि दोस्रोValue को एलिमेन्ट फर्स्टवाल्भ बराबर छ र यो सर्त पनि सन्तोष हुन्छ।

त्यसैले हामी प्रिन्ट (१, २)

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

i = ०,

firstValue = एर [i] [०] // जोडी पहिलो तत्व

दोस्रोValue = arr [i] [1] // जोडी दोस्रो तत्व

firstValue = १, सेकेन्डभल्यु = २

हामी for को लागि जाँच गर्नेछौं यदि यसको मानचित्रमा अवस्थित छ र यो '' 'को रूपमा अवस्थित छ, तब हामी जाँच गर्नेछौं कि सेकेण्डभ्यूको एलिमेन्ट फर्स्टभल्भ बराबर छ कि छैन र यो सर्त पनि सन्तोष हुन्छ।

त्यसैले हामी प्रिन्ट (१, २), (,,,)

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)

जटिलता विश्लेषण

समय जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। हामीले ह्याशम्याप प्रयोग गरेकाले हामी ईन्सर्ट / डिलीट / सर्च ईन गर्न सक्दछौं O (१) समय।

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। हामीले नक्सामा तत्वहरू भण्डार गरेका छौं। ठाउँ जटिलता रैखिक छ।

सन्दर्भ