Эки массивдин барабар экендигин же тең эместигин текшериңиз  


Кыйынчылык деңгээли орто
Көп суралган Accenture Goldman Sachs MAQ o9 чечимдери Taxi4Sure Twilio
согуштук тизме таштанды сорттоо

"Эки массивдин бирдей экендигин же тең эместигин текшериңиз" деген маселе сизге экөө берилгенин билдирет Arrays. Маселе боюнча берилген билдирүүдө, сиз берилген массивдердин барабар же бар эместигин аныкташыңыз керек деп айтылат.

Эки массивдин барабар экендигин же тең эместигин текшериңизтөөнөч

мисал  

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 элементтерин камтыбайт, return false.
    2. Ошол элементтин жыштыгынын 0го барабар экендигин текшерип, эгер true болсо, анда false жалганын кайтарыңыз.
    3. Учурдагы элементтин жыштыгын 1ге азайтыңыз, аны учурдагы элементтин жыштыгынын ордуна сактаңыз.
  5. Бардык баалуулуктар өткөнчө 4-кадамды кайталаңыз.
  6. Чындыкты кайтаруу.

түшүндүрүү

Берилген эки массивдин барабар экендигин же туура келбешин сураган бизге маселе берилди. Муну чечүү үчүн биз колдонобуз Hashing, бул биздин убакытты үнөмдөөгө жардам берет жана убакыттын татаалдыгын төмөндөтөт.

ошондой эле
Бириктирүү иреттөө

Эң биринчи жасай турган нерсе, эки массивдин тең узундугун билиш керек, анткени шарт үчүн, массивдер бирдей болсо, бир шарт аткарылышы керек, жана ал эки массивдин тең узундугу бирдей болушу керек, ошондуктан массивдердин экөөнүн тең узундугун тапканда, биз барабар же жок экендигин текшеришибиз керек, эгер ал бирдей деп табылбаса, анда жалган гана кайтып, андан ары улантуунун кажети жок. Эгер бирдей деп табылса, анда биз гана алдыга жылабыз.

Массивдин ар бир элементинин [] жыштыгын санап, картага сактайбыз. Бир эле элементти эки же үч жолу таптык дейли, анын жыштыгын жаңыртып, 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ге чейин азайтып, кайрадан картага маанисин коёбуз. Демек, бир эле жолу бир нече жолу бар болсо, бул кийинки жолу жардам берет. Бул шарт ошол учурда камтылган. Биз циклден чыккандан кийин, массивде окшош сандардын бардыгы бар экендигин жана массивдерди бирдей кылганды билдирет. Ошондо биз чындыкка кайтып келебиз.

ошондой эле
K Айкын сандары бар эң кичинекей Subarray

Эки массивдин барабар экендигин же тең эместигин текшерүү үчүн 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" массивдеги элементтердин саны. Эгерде бардык элементтер айырмаланып турса, анда биздин картада киргизилген сандардын ар бири үчүн ачкыч мааниси болот. Ошентип, космос татаалдыгы дагы сызыктуу.