জোড়ার একটি অ্যারে দেওয়া এটিতে সমস্ত প্রতিসামান্য জোড়গুলি সন্ধান করুন  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক Capgemini সিসকো ফ্রিচার্জ মুনফ্রোগ ল্যাব অপেরা জুম
বিন্যাস কাটা

সমস্ত প্রতিসামন্ডিক জুটি সন্ধান করুন - আপনাকে একটি এর কিছু জোড়া দেওয়া হয় বিন্যাস। আপনাকে এটিতে প্রতিসাময়িক জোড়গুলি খুঁজে বের করতে হবে। প্রতিযোগিতামূলক জোড়কে প্রতিসম বলা হয় যখন জোড়ায় (ক, খ) এবং (সি, ডি) বলা হয় যেখানে 'বি' 'সি' এর সমান এবং 'এ' 'ডি' এর সমান, অর্থাৎ, (১ , 1) (2, 2) এর প্রতিসম জুটি।

উদাহরণ  

জোড়ার একটি অ্যারে দেওয়া এটিতে সমস্ত প্রতিসামান্য জোড়গুলি সন্ধান করুন

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

সমস্ত প্রতিসামন্ডিক জুড়ি খুঁজতে অ্যালগরিদম  

  1. ঘোষণা করুন ক হ্যাশ মানচিত্র.
  2. যদিও i <এন (অ্যারের দৈর্ঘ্য)
    1. সেট ফার্স্টভ্যালু অ্যারে করতে [i] [0] এবং সেকেন্ডভ্যালু to arr [i] [1]।
    2. সেকেন্ডভ্যালুয়ের মানটি নাল নয় এবং যদি সেকেন্ডভ্যালুয়ের মান ফার্স্টভ্যালুর সমান হয় তা পরীক্ষা করুন
    3. যদি সত্য হয় তবে সেকেন্ডভ্যালু এবং ফার্স্টভ্যালু প্রিন্ট করুন।
    4. অন্যটি হ্যাশম্যাপে ফার্স্টভ্যালু এবং দ্বিতীয় ভ্যালু রাখল।
  3. লুপ বিদ্যমান না হওয়া পর্যন্ত প্রক্রিয়াটি a থেকে d পর্যন্ত পুনরাবৃত্তি করুন।

ব্যাখ্যা

আমরা একটি অ্যারে জোড়া দিয়েছি, সেই অ্যারের অভ্যন্তরে কিছু প্রতিসামান্য জোড় রয়েছে। সমস্যার বিবৃতিটি বলে যে আমাদের একটি অ্যারেতে থাকা সমস্ত প্রতিসাম্য জোড়া খুঁজে পেতে হবে। আমরা কেবল দুটি লুপ ব্যবহার করতে পারি এবং উভয় অ্যারে একের পর এক অনুসরণ করতে পারি। তবে এটি আমাদের আরও বেশি সময় ব্যয় করে এবং আমাদের একটি কার্যকর কোড থাকতে পারে না। তারপরে আমরা প্রথমে নির্দিষ্ট ক্রমে তাদের সাজানোর জন্য আরও ভাল পদ্ধতির ব্যবহার করার চেষ্টা করি তবে এটি আমাদের দক্ষতাও নেয়। সুতরাং একটি দক্ষ প্রোগ্রাম পেতে আমাদের অবশ্যই হ্যাশিং ব্যবহার করতে হবে।

আরো দেখুন
দীর্ঘতম ফিবোনাচি উপযুগের দৈর্ঘ্য

একটি হ্যাশম্যাপ ব্যবহার করে আমরা প্রথমে জোড়ার প্রথম উপাদানটি সংরক্ষণ করি ফার্স্টভ্যালু এবং জোড়া দ্বিতীয় উপাদান সেকেন্ডভ্যালু, আমরা একটি জোড়ের দুটি উপাদানই কী এবং মান হিসাবে ব্যবহার করতে পারি। আমরা একটি জোড়ের কী কী অন্য জোড়ার মান এবং সেই একই জোড়ের মানকে অন্য জোড়ার কীটির সাথে তুলনা করে মানচিত্রে অনুসন্ধান করব।

আমরা একটি হ্যাশম্যাপ ব্যবহার করতে যাচ্ছি জোড়গুলির একটি অ্যারের প্রদত্ত উদাহরণের জন্য বিবেচনা করা যাক, এর মধ্যে সমস্ত প্রতিসামান্য জোড়গুলি সন্ধান করুন

উদাহরণ

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

আমরা অ্যারের জোড়গুলির মানটি প্রথম মূল্য এবং দ্বিতীয় ভ্যালুতে সংরক্ষণ করব এবং তারপরে আমরা এটি পরীক্ষা করব।

i = 0,

ফার্স্টভ্যালু = আরআর [i] [0] // জোড় 1 ম উপাদান

সেকেন্ডভ্যালু = আরআর [i] [1] // জোড় তৃতীয় উপাদান

ফার্স্টভ্যালু = 1, সেকেন্ডভ্যালু = 2

মানচিত্রে মানটির শুল্কের মান রয়েছে কিনা তা আমরা 1 টি যাচাই করে দেখব যাতে এটি মানটিকে মানচিত্রের মধ্যে রাখে।

মানচিত্র = [{1: 2}]

i = 1,

ফার্স্টভ্যালু = আরআর [i] [0] // জোড় 1 ম উপাদান

সেকেন্ডভ্যালু = আরআর [i] [1] // জোড় তৃতীয় উপাদান

ফার্স্টভ্যালু = 30, সেকেন্ডভ্যালু = 40

মানচিত্রে মানটির শুল্কের মান রয়েছে কিনা তা আমরা 30 টি যাচাই করে দেখব যাতে এটি মানটিকে মানচিত্রের মধ্যে রাখে।

মানচিত্র = [{1: 2}, :30 40:XNUMX}]

i = 2,

ফার্স্টভ্যালু = আরআর [i] [0] // জোড় 1 ম উপাদান

সেকেন্ডভ্যালু = আরআর [i] [1] // জোড় তৃতীয় উপাদান

ফার্স্টভ্যালু = 6, সেকেন্ডভ্যালু = 9

মানচিত্রে মানটির শুল্কের মান রয়েছে কিনা তা আমরা 6 টি যাচাই করে দেখব যাতে এটি মানটিকে মানচিত্রের মধ্যে রাখে।

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

i = 3,

ফার্স্টভ্যালু = আরআর [i] [0] // জোড় 1 ম উপাদান

সেকেন্ডভ্যালু = আরআর [i] [1] // জোড় তৃতীয় উপাদান

ফার্স্টভ্যালু = 2, সেকেন্ডভ্যালু = 1

যদি মানচিত্রে এর মান বিদ্যমান থাকে এবং এটি '1' হিসাবে উপস্থিত থাকে তবে আমরা 2 টি যাচাই করে দেখব, তাহলে সেকেন্ডভ্যালুর উপাদানটি ফার্স্টভ্যালুর সমান হয় এবং এই শর্তটিও সন্তুষ্ট হয় কিনা check

আরো দেখুন
ইতিবাচক নিখোঁজ

সুতরাং আমরা মুদ্রণ (1, 2)

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

i = 4,

ফার্স্টভ্যালু = আরআর [i] [0] // জোড় 1 ম উপাদান

সেকেন্ডভ্যালু = আরআর [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)

জটিলতা বিশ্লেষণ  

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। যেহেতু আমরা একটি হ্যাশম্যাপ ব্যবহার করেছি আমরা সন্নিবেশ / মোছা / অনুসন্ধান করতে পারি ও (1) সময়।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। যেহেতু আমরা মানচিত্রে উপাদানগুলি সংরক্ষণ করেছি। স্থান জটিলতা রৈখিক।

তথ্যসূত্র