രണ്ട് അറേകൾ തുല്യമാണോ അല്ലയോ എന്ന് പരിശോധിക്കുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് ഗോൾഡ്മാൻ സാക്സ് MAQ o9 പരിഹാരങ്ങൾ ടാക്സി 4 സ്യൂർ ട്വിలియో
അറേ ഹാഷ് ക്രമപ്പെടുത്തൽ

“രണ്ട് അറേകൾ തുല്യമാണോ അല്ലയോ എന്ന് പരിശോധിക്കുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് രണ്ട് നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണികൾ. തന്നിരിക്കുന്ന അറേകൾ തുല്യമാണോ അല്ലയോ എന്ന് നിങ്ങൾ നിർണ്ണയിക്കേണ്ടതുണ്ടെന്ന് പ്രശ്ന പ്രസ്താവന പറയുന്നു.

രണ്ട് അറേകൾ തുല്യമാണോ അല്ലയോ എന്ന് പരിശോധിക്കുക

ഉദാഹരണം

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. ഒരു ആണോയെന്ന് പരിശോധിക്കുക ഭൂപടം arr2 ഘടകങ്ങൾ അടങ്ങിയിട്ടില്ല, തെറ്റായി മടങ്ങുക.
    2. ആ പ്രത്യേക ഘടകത്തിന്റെ ആവൃത്തി 0 ആണെങ്കിൽ ശരിയാണോയെന്ന് പരിശോധിക്കുക.
    3. നിലവിലെ മൂലകത്തിന്റെ ആവൃത്തി 1 ആക്കി കുറയ്ക്കുക, നിലവിലെ മൂലകത്തിന്റെ ആവൃത്തിയിലുള്ള സ്ഥലത്ത് സൂക്ഷിക്കുക.
  5. എല്ലാ മൂല്യങ്ങളും കടന്നുപോകുന്നതുവരെ നാലാമത്തെ ഘട്ടം ആവർത്തിക്കുക.
  6. ശരിയിലേക്ക് മടങ്ങുക.

വിശദീകരണം

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

നമ്മൾ ആദ്യം ചെയ്യാൻ പോകുന്നത് രണ്ട് അറേകളുടെയും ദൈർഘ്യം കണ്ടെത്തുക എന്നതാണ്, കാരണം ഈ അവസ്ഥയ്ക്ക്, അറേകൾ തുല്യമാണെങ്കിൽ, ഒരു നിബന്ധന പാലിക്കേണ്ടതുണ്ട്, അതാണ് രണ്ട് അറേകളുടെയും നീളം തുല്യമായിരിക്കണം, അതിനാൽ രണ്ട് അറേകളുടെയും ദൈർഘ്യം കണ്ടെത്തുമ്പോൾ, തുല്യമാണോ അല്ലയോ എന്ന് പരിശോധിക്കേണ്ടതുണ്ട്, അത് തുല്യമാണെന്ന് കണ്ടെത്തിയില്ലെങ്കിൽ ഞങ്ങൾ തെറ്റായി മടങ്ങുന്നു, കൂടുതൽ മുന്നോട്ട് പോകേണ്ട ആവശ്യമില്ല. അത് തുല്യമാണെന്ന് കണ്ടെത്തിയാൽ, ഞങ്ങൾ കൂടുതൽ മുന്നോട്ട് പോകും.

അറേ 1 [] ന്റെ ഓരോ ഘടകങ്ങളുടെയും ആവൃത്തികൾ ഞങ്ങൾ മാപ്പിൽ കണക്കാക്കി സംഭരിക്കും. ഒരൊറ്റ മൂലകം രണ്ടോ മൂന്നോ തവണ ഞങ്ങൾ കണ്ടെത്തിയെന്ന് കരുതുക, ഞങ്ങൾ അതിന്റെ ആവൃത്തി 1 വർദ്ധിപ്പിച്ച് വർദ്ധിപ്പിക്കുകയും ആ ഘടകത്തിനൊപ്പം അതേ ആവൃത്തിയിൽ സംഭരിക്കുകയും ചെയ്യുന്നു.

ഉദാഹരണം

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

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

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

അറേ 1 [] കടന്ന് എല്ലാ ഘടകങ്ങളും അവയുടെ ആവൃത്തിയിലുള്ള മാപ്പിൽ ഇടിയതിനുശേഷം നമുക്ക് മാപ്പ് ഇനിപ്പറയുന്നതായി ഉണ്ട്.

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 !!

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ലീനിയർ സമയ സങ്കീർണ്ണത കൈവരിക്കാൻ ഹാഷ്‌മാപ്പ് ഉപയോഗിക്കുന്നത് ഞങ്ങളെ അനുവദിച്ചു, അല്ലാത്തപക്ഷം കൂടുതൽ സമയം എടുക്കുമായിരുന്നു.

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

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