Ελέγξτε εάν δύο συστοιχίες είναι ίσες ή όχι


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Accenture Goldman Sachs MAQ o9 λύσεις Ταξί4Sure 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. Ελέγξτε εάν a χάρτη δεν περιέχει στοιχεία arr2, επιστροφή false.
    2. Ελέγξτε εάν η συχνότητα αυτού του συγκεκριμένου στοιχείου είναι ίση με 0 εάν είναι αληθής και μετά επιστρέψτε ψευδής.
    3. Μειώστε τη συχνότητα του τρέχοντος στοιχείου κατά 1, αποθηκεύστε το στη θέση της συχνότητας του τρέχοντος στοιχείου.
  5. Επαναλάβετε το 4ο βήμα μέχρι να διασταυρωθούν όλες οι τιμές.
  6. Επιστροφή αληθινή.

εξήγηση

Μας δίνεται ένα πρόβλημα που ζητά να μάθουμε αν οι δύο συστοιχίες είναι ίσες ή όχι. Για να το λύσουμε αυτό θα χρησιμοποιήσουμε Hashing, βοηθά στην εξοικονόμηση χρόνου και μειώνει την πολυπλοκότητα του χρόνου.

Το πρώτο πράγμα που πρόκειται να κάνουμε είναι να μάθουμε το μήκος και των δύο συστοιχιών, επειδή για την κατάσταση, εάν οι συστοιχίες είναι ίσες, πρέπει να πληρούται μία προϋπόθεση και αυτό είναι το μήκος και των δύο συστοιχιών πρέπει να είναι ίσο, όταν εντοπίσουμε το μήκος και των δύο συστοιχιών, απλώς πρέπει να ελέγξουμε αν είναι ίσο ή όχι, αν δεν βρεθεί ίσο, απλά επιστρέφουμε ψευδές και δεν χρειάζεται να προχωρήσουμε περαιτέρω. Εάν βρεθεί ότι είναι ίσο, τότε μόνο θα προχωρήσουμε πιο μακριά.

Θα μετρήσουμε και θα αποθηκεύσουμε τις συχνότητες κάθε στοιχείου του πίνακα1 [] στο χάρτη. Ας υποθέσουμε ότι βρίσκουμε ένα στοιχείο δύο ή τρεις φορές, απλώς ενημερώνουμε και αυξάνουμε τη συχνότητά του κατά 1 και αποθηκεύουμε στην ίδια συχνότητα μαζί με αυτό το στοιχείο.

Παράδειγμα

Ας εξετάσουμε ένα παράδειγμα:

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

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

Αφού διασχίσουμε τον πίνακα1 [] και βάζουμε όλα τα στοιχεία με τις συχνότητές τους στον χάρτη, έχουμε τον χάρτη ως εξής.

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

Καθώς έχουμε τις τιμές στο χάρτη μας, πρέπει να διασχίσουμε τη δεύτερη συστοιχία και να ελέγξουμε εάν ένας χάρτης έχει στοιχεία array2, εάν δεν περιέχει τα στοιχεία array2 [] τότε επιστρέφουμε false. Θα ελέγξουμε, εάν η συχνότητα του τρέχοντος στοιχείου είναι ίση με 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 !!

Κωδικός Java για να ελέγξετε αν δύο πίνακες είναι ίσες ή όχι

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) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Η χρήση του HashMap μας επέτρεψε να επιτύχουμε γραμμική πολυπλοκότητα χρόνου αλλιώς θα χρειαζόταν πολύ περισσότερο χρόνο.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Εάν όλα τα στοιχεία θα είναι διαφορετικά, ο χάρτης μας θα έχει τιμή-κλειδί για καθένα από τους αριθμούς στην είσοδο. Έτσι, η πολυπλοκότητα του διαστήματος είναι επίσης γραμμική.