ജോഡികളുടെ ഒരു നിര നൽകി അതിൽ എല്ലാ സമമിതി ജോഡികളും കണ്ടെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ കാപ്ജെമിനിയും സിസ്കോ ഫ്രീചാർജ് മൂൺഫ്രോഗ് ലാബുകൾ Opera സോം
അറേ ഹാഷ്

എല്ലാ സമമിതി ജോഡികളും കണ്ടെത്തുക - നിങ്ങൾക്ക് ഒരു ജോഡി ജോഡി നൽകിയിരിക്കുന്നു ശ്രേണി. ഇതിലെ സമമിതി ജോഡികൾ നിങ്ങൾ കണ്ടെത്തണം. (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. ഒരു പ്രഖ്യാപിക്കുക ഹാഷ്‌മാപ്പ്.
  2. അതേസമയം i <n (അറേയുടെ നീളം)
    1. ഗണം firstValue അറേയിലേക്ക് [i] [0] ഒപ്പം സെക്കൻഡ് വാല്യു to arr [i] [1].
    2. സെക്കൻഡ് വാല്യൂവിന്റെ മൂല്യം അസാധുവല്ലെന്നും സെക്കൻഡ് വാല്യുവിന്റെ മൂല്യം ഫസ്റ്റ്വാലുവിന് തുല്യമാണോയെന്നും പരിശോധിക്കുക
    3. ശരിയാണെങ്കിൽ, സെക്കൻഡ് വാല്യുവും ഫസ്റ്റ് വാല്യൂവും പ്രിന്റുചെയ്യുക.
    4. മറ്റൊന്ന് ഫസ്റ്റ് വാല്യുവും സെക്കൻഡ് വാല്യൂവും ഹാഷ്‌മാപ്പിൽ ഇടുക.
  3. ലൂപ്പ് നിലനിൽക്കുന്നതുവരെ പ്രക്രിയ a മുതൽ d വരെ ആവർത്തിക്കുക.

വിശദീകരണം

ഞങ്ങൾ ഒരു അറേ ജോഡികൾ നൽകി, ആ അറേയ്ക്കുള്ളിൽ ചില സമമിതി ജോഡികൾ നിലവിലുണ്ട്. ഒരു അറേയിൽ നിലവിലുള്ള എല്ലാ സമമിതി ജോഡികളും ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ടെന്ന് പ്രശ്ന പ്രസ്താവന പറയുന്നു. നമുക്ക് രണ്ട് ലൂപ്പുകൾ ഉപയോഗിക്കാനും രണ്ട് അറേകളും ഓരോന്നായി സഞ്ചരിക്കാനും കഴിയും. എന്നാൽ ഇത് ഞങ്ങൾക്ക് കൂടുതൽ സമയ സങ്കീർണ്ണത ചിലവാക്കുന്നു, മാത്രമല്ല ഞങ്ങൾക്ക് കാര്യക്ഷമമായ ഒരു കോഡ് ഇല്ല. ഒരു പ്രത്യേക ക്രമത്തിൽ ആദ്യം അവയെ അടുക്കുന്നതിന് ഒരു മികച്ച സമീപനം ഉപയോഗിക്കാൻ ഞങ്ങൾ ശ്രമിക്കുന്നു, മാത്രമല്ല ഇത് ഞങ്ങളുടെ കാര്യക്ഷമതയും എടുക്കുന്നു. അതിനാൽ കാര്യക്ഷമമായ ഒരു പ്രോഗ്രാം ലഭിക്കാൻ ഞങ്ങൾ ഹാഷിംഗ് ഉപയോഗിക്കണം.

ഒരു ഹാഷ്‌മാപ്പ് ഉപയോഗിക്കുന്നതിലൂടെ, ഞങ്ങൾ ആദ്യം ജോഡിയുടെ ആദ്യ ഘടകം സംഭരിക്കുന്നു firstValue ഒപ്പം ജോഡിയുടെ രണ്ടാമത്തെ ഘടകം സെക്കൻഡ് വാല്യു, ഒരു ജോഡിയുടെ രണ്ട് ഘടകങ്ങളും ഒരു കീയായും മൂല്യമായും ഉപയോഗിക്കാം. ഒരു ജോഡിയുടെ കീ മറ്റൊരു ജോഡിയുടെ മൂല്യവും അതേ ജോഡിയുടെ മൂല്യവും മറ്റൊരു ജോഡിയുടെ കീയുമായി താരതമ്യപ്പെടുത്തി ഞങ്ങൾ ഒരു മാപ്പിൽ തിരയും.

ഞങ്ങൾ ഒരു ഹാഷ്‌മാപ്പ് ഉപയോഗിക്കാൻ പോകുന്നു ജോഡികളുടെ ഒരു നിര നൽകിയതിന് ഒരു ഉദാഹരണം നോക്കാം, അതിൽ എല്ലാ സമമിതി ജോഡികളും കണ്ടെത്തുക

ഉദാഹരണം

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

അറേയുടെ ജോഡി മൂല്യം ഫസ്റ്റ് വാല്യൂ, സെക്കൻഡ് വാല്യൂ എന്നിവയിലേക്ക് ഞങ്ങൾ സംഭരിക്കും, തുടർന്ന് ഞങ്ങൾ അത് പരിശോധിക്കും.

i = 0,

firstValue = arr [i] [0] // ജോഡി 1st ഘടകം

secondValue = arr [i] [1] // ജോഡി രണ്ടാമത്തെ ഘടകം

firstValue = 1, secondValue = 2

1 മാപ്പിന് ഒരു മൂല്യമുണ്ടോയെന്നും അവസ്ഥ തെറ്റാണെന്നും ഞങ്ങൾ XNUMX പരിശോധിക്കും, അതിനാൽ ഇത് മൂല്യത്തെ മാപ്പിൽ ഇടുന്നു.

മാപ്പ് = [{1: 2}]

i = 1,

firstValue = arr [i] [0] // ജോഡി 1st ഘടകം

secondValue = arr [i] [1] // ജോഡി രണ്ടാമത്തെ ഘടകം

firstValue = 30, secondValue = 40

30 മാപ്പിന് ഒരു മൂല്യമുണ്ടോയെന്നും അവസ്ഥ തെറ്റാണെന്നും ഞങ്ങൾ XNUMX പരിശോധിക്കും, അതിനാൽ ഇത് മൂല്യത്തെ മാപ്പിൽ ഇടുന്നു.

മാപ്പ് = [{1: 2}, {30:40}]

i = 2,

firstValue = arr [i] [0] // ജോഡി 1st ഘടകം

secondValue = arr [i] [1] // ജോഡി രണ്ടാമത്തെ ഘടകം

firstValue = 6, secondValue = 9

6 മാപ്പിന് ഒരു മൂല്യമുണ്ടോയെന്നും അവസ്ഥ തെറ്റാണെന്നും ഞങ്ങൾ XNUMX പരിശോധിക്കും, അതിനാൽ ഇത് മൂല്യത്തെ മാപ്പിൽ ഇടുന്നു.

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

i = 3,

firstValue = arr [i] [0] // ജോഡി 1st ഘടകം

secondValue = arr [i] [1] // ജോഡി രണ്ടാമത്തെ ഘടകം

firstValue = 2, secondValue = 1

ഒരു മാപ്പിൽ മൂല്യമുണ്ടോയെന്നും അത് '1' ആണെന്നും ഞങ്ങൾ 2 പരിശോധിക്കും, സെക്കൻഡ് വാലുവിന്റെ ഘടകം ഫസ്റ്റ് വാല്യുവിനു തുല്യമാണോ എന്നും ഈ അവസ്ഥയും തൃപ്തികരമാണോ എന്നും ഞങ്ങൾ പരിശോധിക്കും.

അതിനാൽ ഞങ്ങൾ അച്ചടിക്കുന്നു (1, 2)

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

i = 4,

firstValue = arr [i] [0] // ജോഡി 1st ഘടകം

secondValue = arr [i] [1] // ജോഡി രണ്ടാമത്തെ ഘടകം

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)

എല്ലാ സമമിതി ജോഡികളും കണ്ടെത്താനുള്ള ജാവ പ്രോഗ്രാം

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” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ ഒരു ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ചതിനാൽ ഉൾപ്പെടുത്തൽ / ഇല്ലാതാക്കൽ / തിരയൽ എന്നിവ നടത്താൻ കഴിയും O (1) സമയം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ‌ മാപ്പിൽ‌ ഘടകങ്ങൾ‌ സംഭരിച്ചതിനാൽ‌. സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.

അവലംബം