જોડીનો એરે આપ્યો તેમાં બધી સપ્રમાણ જોડી શોધો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન કેપજેમિની સિસ્કો ફ્રીચાર્જ મૂનફ્રોગ લેબ્સ ઓપેરા Xome
અરે હેશ

બધી સપ્રમાણ જોડી શોધો - તમને કેટલીક જોડી આપવામાં આવે છે એરે. તમારે તેમાં સપ્રમાણ જોડી શોધવા પડશે. જ્યારે જોડીમાં (એ, બી) અને (સી, ડી) કહેવામાં આવે છે ત્યારે સપ્રમાણ જોડીને સપ્રમાણ કહેવાય છે, જેમાં 'બી' 'સી' ની બરાબર છે અને 'એ' 'ડી' ની બરાબર છે, એટલે કે, (1 , 2) (2, 1) ની સપ્રમાણ જોડી છે.

ઉદાહરણ

જોડીનો એરે આપ્યો તેમાં બધી સપ્રમાણ જોડી શોધો

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

બધા સપ્રમાણ જોડી શોધવા માટે એલ્ગોરિધમ

  1. ઘોષણા કરો એ હેશમેપ.
  2. જ્યારે હું <એન (એરેની લંબાઈ)
    1. સેટ પ્રથમ કિંમત એરે કરવા માટે [i] [0] અને બીજું મૂલ્ય to arr [i] [1].
    2. તપાસો કે શું સેકંડવueલ્યુનું મૂલ્ય નલ નથી અને જો સેકંડવalલ્યૂનું મૂલ્ય ફર્સ્ટવalલ્યુની બરાબર છે
    3. જો સાચું હોય, તો પછી સેકન્ડવalલ્યુ અને ફર્સ્ટવalલૂ પ્રિન્ટ કરો.
    4. બાકી હ Hashશમેપમાં પ્રથમ વalલ્યુ અને સેકન્ડવalલ્યૂ મૂકો.
  3. લૂપ અસ્તિત્વમાં ન હોય ત્યાં સુધી પ્રક્રિયાને એક થી ડી સુધી પુનરાવર્તન કરો.

સમજૂતી

આપણે એરે જોડી આપી છે, એરે ની અંદર કેટલાક સપ્રમાણ જોડી અસ્તિત્વમાં છે. સમસ્યા નિવેદન કહે છે કે આપણે એરેમાં અસ્તિત્વમાં છે તે બધા સપ્રમાણ જોડી શોધવા પડશે. અમે ફક્ત બે લૂપ્સનો ઉપયોગ કરી શકીએ છીએ અને બંને એરેને એક પછી એક પસાર કરી શકીએ છીએ. પરંતુ તે આપણને વધુ સમયની જટિલતા માટે ખર્ચ કરે છે અને અમારી પાસે કાર્યક્ષમ કોડ હોઈ શકતો નથી. પછી અમે તેમને ચોક્કસ ક્રમમાં ગોઠવવા માટે વધુ સારી રીતનો ઉપયોગ કરવાનો પ્રયાસ કરીએ છીએ પરંતુ તે આપણી કાર્યક્ષમતાને પણ લે છે. તેથી એક કાર્યક્ષમ પ્રોગ્રામ મેળવવા માટે આપણે હેશીંગનો ઉપયોગ કરવો આવશ્યક છે.

હેશમેપનો ઉપયોગ કરીને, અમે જોડીનું પ્રથમ તત્વ પહેલા સંગ્રહિત કરીએ છીએ પ્રથમ કિંમત અને જોડીનો બીજો તત્વ બીજું મૂલ્ય, આપણે જોડીનાં બંને તત્વોનો ઉપયોગ કી અને મૂલ્ય તરીકે કરી શકીએ છીએ. અમે એક જોડની ચાવી બીજી જોડીની કિંમત અને તે જ જોડીની કિંમત બીજી જોડીની ચાવી સાથે સરખાવીને એક નકશામાં શોધીશું.

આપણે હેશમેપનો ઉપયોગ કરવા જઈ રહ્યા છીએ, ચાલો જોડીના એરે આપેલ ઉદાહરણ માટે ધ્યાનમાં લઈએ, તેમાં બધી સપ્રમાણ જોડી શોધી કા Findીએ.

ઉદાહરણ

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

આપણે એરેની જોડી કિંમત ફર્સ્ટવalલ્યુ અને સેકન્ડવalલ્યુમાં સંગ્રહિત કરીશું અને પછી આપણે તેની તપાસ કરીશું.

i = 0,

ફર્સ્ટવalલ્યુ = એઆરઆર [i] [0] // જોડી 1 લી તત્વ

સેકંડવલ્યુ = એઆરઆર [i] [1] // જોડી 2 જી તત્વ

ફર્સ્ટવલ્યુ = 1, સેકંડવલ્યુ = 2

અમે 1 ની તપાસ કરીશું કે જો તેના નકશામાં મૂલ્ય છે અને શરત ખોટી છે તેથી તે નકશામાં બંને મૂલ્ય મૂકે છે.

નકશો = [{1: 2}]

i = 1,

ફર્સ્ટવalલ્યુ = એઆરઆર [i] [0] // જોડી 1 લી તત્વ

સેકંડવલ્યુ = એઆરઆર [i] [1] // જોડી 2 જી તત્વ

ફર્સ્ટવલ્યુ = 30, સેકંડવલ્યુ = 40

અમે 30 ની તપાસ કરીશું કે જો તેના નકશામાં મૂલ્ય છે અને શરત ખોટી છે તેથી તે નકશામાં બંને મૂલ્ય મૂકે છે.

નકશો = [{1: 2}, :30 40:XNUMX}]

i = 2,

ફર્સ્ટવalલ્યુ = એઆરઆર [i] [0] // જોડી 1 લી તત્વ

સેકંડવલ્યુ = એઆરઆર [i] [1] // જોડી 2 જી તત્વ

ફર્સ્ટવલ્યુ = 6, સેકંડવલ્યુ = 9

અમે 6 ની તપાસ કરીશું કે જો તેના નકશામાં મૂલ્ય છે અને શરત ખોટી છે તેથી તે નકશામાં બંને મૂલ્ય મૂકે છે.

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

i = 3,

ફર્સ્ટવalલ્યુ = એઆરઆર [i] [0] // જોડી 1 લી તત્વ

સેકંડવલ્યુ = એઆરઆર [i] [1] // જોડી 2 જી તત્વ

ફર્સ્ટવલ્યુ = 2, સેકંડવલ્યુ = 1

જો આપણે નકશામાં તેનું મૂલ્ય અસ્તિત્વમાં છે અને તે '1' તરીકે અસ્તિત્વમાં છે, તો આપણે 2 ચકાસીશું, પછી જો આપણે સેકંડવલ્યુનું તત્ત્વ ફર્સ્ટવલ્યુની બરાબર છે અને આ સ્થિતિ પણ સંતોષશે તો.

તેથી અમે છાપો (1, 2)

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

i = 4,

ફર્સ્ટવalલ્યુ = એઆરઆર [i] [0] // જોડી 1 લી તત્વ

સેકંડવલ્યુ = એઆરઆર [i] [1] // જોડી 2 જી તત્વ

ફર્સ્ટવલ્યુ = 9, સેકંડવલ્યુ = 6

આપણે for ની તપાસ કરીશું કે જો તેના નકશામાં મૂલ્ય અસ્તિત્વમાં છે અને તે '' 'તરીકે અસ્તિત્વમાં છે, તો આપણે તપાસ કરીશું કે સેકન્ડવalલ્યુનું તત્ત્વ ફર્સ્ટવalલ્યુની બરાબર છે કે કેમ અને આ સ્થિતિ પણ સંતોષે છે.

તેથી અમે (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)

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. આપણે હેશમેપનો ઉપયોગ કર્યો હોવાથી અમે નિવેશ / કા deleી નાખવા / શોધ કરી શકીએ છીએ ઓ (1) સમય.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. કારણ કે આપણે નકશામાં તત્વો સંગ્રહિત કર્યા છે. જગ્યાની જટિલતા રેખીય છે.

સંદર્ભ