Хоёр массив тэнцүү байгаа эсэхийг шалгана уу


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accenture Goldman Sachs MAQ o9 шийдэл Такси4 Twilio
Array Хаш Ангилах

“Хоёр массив тэнцүү байгаа эсэхийг шалгаарай” гэсэн асуудалд танд хоёрыг өгсөн байна массивууд. Асуудлын тайлбарт өгөгдсөн массивууд тэнцүү эсвэл үгүй ​​эсэхийг тодорхойлох ёстой гэж хэлсэн.

Хоёр массив тэнцүү байгаа эсэхийг шалгана уу

Жишээ нь

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 элемент агуулаагүй тул false гэсэн утгатай буцаана.
    2. Тухайн элементийн давтамж үнэн бол 0-тэй тэнцүү байгаа эсэхийг шалгаад дараа нь худал гэсэн утгатай болно.
    3. Одоогийн элементийн давтамжийг 1-ээр багасгаж, одоогийн элементийн давтамжийн тэр газарт хадгална.
  5. Бүх утгыг давах хүртэл 4-р алхамыг давт.
  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 болгож бууруулж, газрын зураг дээр дахин утгыг оруулна. Тиймээс, ижил тоо хэд хэдэн удаа байвал энэ нь дараагийн удаа туслах болно. Энэ нөхцлийг тухайн тохиолдолд оруулсан болно. Бид давталтаас гарсны дараа массивтай ижил тоонууд бүгд ижил бөгөөд массивууд тэнцүү болно гэсэн үг юм. Дараа нь бид үнэн эргэж ирнэ.

Хоёр массив тэнцүү байгаа эсэхийг шалгах 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) хаана "N" нь массив дахь элементүүдийн тоо юм. HashMap-ийг ашиглах нь цаг хугацааны шугаман нарийн төвөгтэй байдалд хүрэх боломжийг олгосон бөгөөд ингэснээр илүү их цаг хугацаа шаардагдах байсан.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Хэрэв бүх элементүүд ялгаатай байх юм бол манай газрын зураг оролтын тоо тус бүрт түлхүүр утгатай байх болно. Тиймээс сансрын нарийн төвөгтэй байдал нь мөн шугаман юм.