Екі массивтің тең немесе тең еместігін тексеріңіз


Күрделілік дәрежесі орта
Жиі кіреді Accenture Голдман Сакс MAQ o9 шешімдері Такси4Әрине Twilio
Array Hash Сұрыптау

«Екі массивтің тең екендігін немесе тең еместігін тексеріңіз» деген есеп сізге екі берілгенін көрсетеді массивтер. Проблемалық есепте берілген массивтердің тең немесе тең еместігін анықтау керек екендігі айтылады.

Екі массивтің тең немесе тең еместігін тексеріңіз

мысал

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-ге жаңартып, көбейтіп, сол жиілікте сол элементпен бірге сақтаймыз.

мысал

Мысалды қарастырайық:

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» - бұл массивтегі элементтер саны. Егер барлық элементтер ерекшеленетін болса, біздің картада кірістегі сандардың әрқайсысы үшін кілт мәні болады. Сонымен, ғарыш күрделілігі де сызықтық болып табылады.