તપાસો કે બે એરે સમાન છે કે નહીં


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એક્સેન્ચર ગોલ્ડમૅન સૅશ MAQ o9 ઉકેલો ટેક્સી 4 સ્યુર Twilio
અરે હેશ સોર્ટિંગ

સમસ્યા "બે એરે સમાન છે કે નહીં તે તપાસો" કહે છે કે તમને બે આપવામાં આવ્યા છે એરે. સમસ્યાનું નિવેદન કહે છે કે આપેલ એરે સમાન છે કે નહીં તે તમારે નક્કી કરવું પડશે.

તપાસો કે બે એરે સમાન છે કે નહીં

ઉદાહરણ

arr1[] = { 1, 4, 2, 5, 2 };
arr2[] = { 2, 1, 5, 4, 2 };
Yes, Arrays are equal !!
arr1[] = { 1, 3, 2, 7, 2 };
arr2[] = { 2, 1, 5, 3, 2 };
No, Arrays are not equal !!

બે એરે સમાન છે કે નહીં તે ચકાસવા માટે એલ્ગોરિધમ

  1. બંને એરેની લંબાઈ સેટ કરો l1 અને l2 અનુક્રમે.
  2. તપાસો કે બંને લંબાઈ સમાન નથી, જો સાચી હોય તો ખોટી પરત ફરો.
  3. નકશામાં દરેક તત્વની ફ્રીક્વન્સીઝને સ્ટોર અને ગણતરી કરો.
  4. બીજા એરેનો પ્રવાસ કરવો,
    1. તપાસો જો નકશો એઆર 2 તત્વો શામેલ નથી, ખોટા પાછા ફરો.
    2. તે તત્વની આવર્તન 0 ની બરાબર છે કે કેમ તે તપાસો જો ખોટું વળતર.
    3. વર્તમાન તત્વની આવર્તન 1 દ્વારા ઘટાડો, તેને વર્તમાન તત્વની આવર્તનની તે જગ્યાએ સંગ્રહિત કરો.
  5. જ્યાં સુધી બધા મૂલ્યો ઓળંગી ન જાય ત્યાં સુધી ચોથા પગલાંને પુનરાવર્તિત કરો.
  6. સાચું પાછા ફરો.

સમજૂતી

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

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

અમે નકશામાં એરે 1 [] ના દરેક તત્વની આવર્તનની ગણતરી અને સંગ્રહ કરીશું. માની લો કે આપણે એક કે તત્વને બે કે ત્રણ વાર શોધીએ છીએ, અમે ફક્ત તેની આવૃત્તિ 1 દ્વારા વધારીએ છીએ અને તે જ આવર્તન પર તે તત્વ સાથે સંગ્રહ કરીએ છીએ.

ઉદાહરણ

ચાલો આપણે એક ઉદાહરણ ધ્યાનમાં લઈએ:

arr1 [] = {1, 4, 2, 5, 2};

arr2 [] = {2, 1, 5, 4, 2};

એરે 1 ને ટ્રversવર્સ કર્યા પછી [] અને બધા તત્વોને તેમની ફ્રીક્વન્સીઝ સાથે નકશામાં મૂક્યા પછી નીચે આપણી પાસે નકશો છે.

myMap={1:1, 2:2, 4:1, 5:1}

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

સી ++ કોડ તપાસવા માટે કે બે એરે સમાન છે કે નહીં

#include <unordered_map>
#include<iostream>

using namespace std;

bool areTwoArrayEqual(int arr1[], int arr2[], int l1, int l2)
{
    if (l1 !=l2)
        return false;

    unordered_map<int, int> myMap;
    for (int i = 0; i < l1; i++)
    {
        myMap[arr1[i]]++;
    }
    for (int i = 0; i < l1; i++)
    {
        if (myMap.find(arr2[i]) == myMap.end())
            return false;

        if (myMap[arr2[i]] == 0)
            return false;

        myMap[arr2[i]]--;
    }

    return true;
}
int main()
{
    int arr1[] = { 1, 4, 2, 5, 2 };
    int arr2[] = { 2, 1, 5, 4, 2 };

    int l1 = sizeof(arr1) / sizeof(int);
    int l2 = sizeof(arr2) / sizeof(int);

    if (areTwoArrayEqual(arr1, arr2, l1, l2))
        cout << "Yes, Arrays are equal !!";
    else
        cout << "No, Arrays are not equal !!";
    return 0;
}
Yes, Arrays are equal !!

બે એરે સમાન છે કે નહીં તે તપાસવા માટે જાવા કોડ

import java.util.*;

class twoArrayEqual
{
    public static boolean areTwoArrayEqual(int arr1[], int arr2[])
    {
        int l1 = arr1.length;
        int l2 = arr2.length;

        if (l1 != l2)
            return false;

        Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
        int count = 0;
        for (int i = 0; i < l1; i++)
        {
            if (myMap.get(arr1[i]) == null)
                myMap.put(arr1[i], 1);
            else
            {
                count = myMap.get(arr1[i]);
                count++;
                myMap.put(arr1[i], count);
            }
        }
        for (int i = 0; i < l1; i++)
        {
            if (!myMap.containsKey(arr2[i]))
                return false;

            if (myMap.get(arr2[i]) == 0)
                return false;

            count = myMap.get(arr2[i]);
            --count;
            myMap.put(arr2[i], count);
        }

        return true;
    }
    public static void main(String[] args)
    {
        int arr1[] = { 1, 4, 2, 5, 2 };
        int arr2[] = { 2, 1, 5, 4, 2 };

        if (areTwoArrayEqual(arr1, arr2))
            System.out.println("Yes, Arrays are equal !!");
        else
            System.out.println("No, Arrays are not equal !!");
    }
}
Yes, Arrays are equal !!

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

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. હેશમેપનો ઉપયોગ કરવાથી અમને રેખીય સમયની જટિલતા પ્રાપ્ત કરવાની મંજૂરી મળી, નહીં તો તે વધુ સમય લેત.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. જો બધા તત્વો અલગ હશે, તો અમારા નકશામાં ઇનપુટની દરેક સંખ્યા માટે કી-મૂલ્ય હશે. આમ જગ્યા જટિલતા પણ રેખીય છે.