ሁለት ድርድር እኩል መሆን አለመሆኑን ያረጋግጡ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ Accenture ጎልድማን ሳክስ 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. የሁለቱም ድርድሮች ርዝመት ወደ ላይ ያዘጋጁ l1l2 በቅደም ተከተል.
  2. ሁለቱም ርዝመቶች እኩል ካልሆኑ ያረጋግጡ ፣ እውነት ከሆነ ፣ በሐሰት ይመለሱ።
  3. የእያንዳንዱን ንጥረ ነገር ድግግሞሽ በካርታው ውስጥ ያከማቹ እና ይቁጠሩ ፡፡
  4. ሁለተኛውን ድርድር በማለፍ ላይ ፣
    1. ከሆነ ያረጋግጡ ካርታ የ arr2 አባላትን አልያዘም ፣ ሐሰትን ይመልሱ።
    2. የዚያ የተወሰነ ንጥረ ነገር ድግግሞሽ እውነት ከሆነ ከ 0 ጋር እኩል መሆኑን ያረጋግጡ ከዚያ ሐሰትን ይመልሱ።
    3. የአሁኑን ንጥረ ነገር ድግግሞሽ በ 1 ይቀንሱ ፣ የአሁኑን ንጥረ ነገር ድግግሞሽ ወደዚያ ቦታ ያከማቹ።
  5. ሁሉም እሴቶች እስኪሻገሩ ድረስ 4 ኛ ደረጃን ይድገሙ።
  6. ወደ እውነት ተመለስ

ማስረጃ

የተሰጠው ሁለት ድርድር እኩል መሆን አለመሆኑን ለማጣራት የሚጠይቅ ችግር ተሰጥቶናል ፡፡ ይህንን ለመፍታት እኛ ልንጠቀምበት ነው ሃምሽንግ፣ ጊዜያችንን ለመቆጠብ ይረዳል እና የጊዜን ውስብስብነት ይቀንሰዋል።

እኛ ማድረግ ያለብን የመጀመሪያው ነገር የሁለቱን ድርድር ርዝመት ማወቅ ነው ምክንያቱም ለጉዳዩ ፣ ድርድሮች እኩል ከሆኑ አንድ ሁኔታ መሟላት አለበት ፣ እናም የሁለቱም ድርድር ርዝመት እኩል መሆን አለበት ፡፡ የሁለቱም ድርድሮች ርዝመት ስናገኝ እኩል መሆን አለመሆኑን ማረጋገጥ ያስፈልገናል ፣ እኩል ሆኖ ካልተገኘ ሐሰት እንመልሳለን እናም ወደ ፊት መቀጠል አያስፈልገንም ፡፡ እኩል ሆኖ ከተገኘ ከዚያ በኋላ ብቻ ወደ ፊት እንሸጋገራለን ፡፡

የእያንዳንዱን የ 1 [1] ንጥል ድግግሞሽ ብዛት በካርታው ውስጥ እንቆጥረዋለን እናከማቸዋለን ፡፡ አንድ ወይም ሁለት ጊዜ አንድ ነጠላ ንጥረ ነገር እናገኛለን እንበል ፣ አንድ ጊዜ ብቻ ድግግሞሹን በ XNUMX እናሻሽለዋለን እና እንጨምራለን እና ከዚያ ተመሳሳይ አካል ጋር በዚያው ተመሳሳይ ድግግሞሽ ላይ እናከማቸዋለን ፡፡

ለምሳሌ

እስቲ አንድ ምሳሌ እንመልከት-

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 ዝቅ እና እንደገና እሴቱን ወደ ካርታው ውስጥ እንጨምረዋለን ፡፡ ስለዚህ ይህ ተመሳሳይ ቁጥር ከአንድ ጊዜ በላይ ካለ ለሚቀጥለው ጊዜ ይረዳል ፡፡ ይህ ሁኔታ በዚያ ሁኔታ ውስጥ ተካትቷል ፡፡ አንዴ ከሉፉ ከወጣን በኋላ ፣ ሁሉም ቁጥሮች በምድቡ ውስጥ ተመሳሳይነት አለን እና አሰራሮችን እኩል እናደርጋለን ማለት ነው ፡፡ ያኔ ወደ እውነት እንመለሳለን ፡፡

ሁለት ድርድር እኩል መሆን አለመሆኑን ለማጣራት የ C ++ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ሃሽ ማፕን በመጠቀም መስመራዊ የጊዜ ውስብስብነትን ለማሳካት አስችሎናል ፣ ሌላ ብዙ ጊዜ ሊወስድ ይችላል።

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ሁሉም አካላት ተለይተው የሚታወቁ ከሆነ ካርታችን በግብአት ውስጥ ላሉት ቁጥሮች ቁልፍ ዋጋ ይኖረዋል ፡፡ ስለዚህ የቦታ ውስብስብነት እንዲሁ መስመራዊ ነው።