Жиым басқа массивтің ішкі жиыны екенін табыңыз  


Күрделілік дәрежесі оңай
Жиі кіреді Акколит GE Healthcare Qualcomm
Array Екілік іздеу Hash іздеу Сұрыптау

«Массивтің басқа массивтің жиынтығы екенін табу» мәселесінде сізге arra1 [] және массив2 [] екі массиві берілгендігі айтылған. Берілген массивтер сұрыпталмаған түрде берілген. Сіздің міндетіңіз - массив2 [] жиымының [[[жиымның]] жиынтығы екенін табу.

мысал  

Жиым басқа массивтің ішкі жиыны екенін табыңыз

arr1= [1,4,5,7,8,2]
arr2= [1,7,2,4]
arr2 [] is a subset of arr1 [].
arr1= [21,4,5,2,18,3]
arr2= [1,4,2,3]
arr2 [] is not a subset of arr1 [].

Алгоритм  

  1. Кірістірілген циклды ашыңыз.
  2. I-ді 0-ге, j-ді 0-ге теңестіріңіз.
  3. уақыт i массивтің ұзындығынан кіші [].
    1. уақыт j массивтің ұзындығынан кіші [].
      1. Егер arr2 [i] arr [j] -ге тең болса, онда break.
  4. If j m-ге тең болса, жалған мәнін қайтарыңыз.
  5. Ақиқатқа оралу

Түсіндіру

Біздің міндетіміз: массив екінші - жиымның ішкі жиыны. Сонымен, біздің негізгі идеямыз - кірістірілген циклды пайдалану және әрбір элементті тексеру және массивтің барлық элементтері 1 жиымында кездеседі, яғни массив2 жиымның жиыны болып табылады.

Массив1 және массив2 ішіндегі енгізу ретінде мысал алайық

мысал

arr1 [] = {11, 1, 13, 21, 3, 7}; arr2 [] = {11, 3, 7, 1};

Массив0-дің 2-ші индексінен бастап, массивтің0-ші 2 индексі [i] жиымында ұқсас санды тапқанын тексереміз, иә ол оны 1 деп тапты. Сонымен, біз циклды бұзып, i ++ жасаймыз.

Сондай-ақ, қараңыз
Ең ұзын Битоникалық Сабақтастық

1 массивтің 2 индексінен [1 массивтің 2 индексі [1] жиымынан ұқсас санды тапқанын тексереміз, иә оны 3 деп тапты. Сонымен, біз циклды бұзып, i ++ жасаймыз .

Массивтің [2] 2 индексінен бастап, массивтің 2 индексі 2 массивінде [i] ұқсас санды тапқанын тексереміз және ол оны 1 деп тапты. Сонымен циклды бұзып, i ++ жасаймыз.

Массивтің [1] 2 индексінен бастап, массивтердің 1 индексі 2 массивінде [i] ұқсас санды тапқанын және 1 тапқанын тексереміз. Сонымен, біз циклды бұзып, i ++ жасаймыз.

Егер (j = = m) түрінде көрсетілген шарт дегеніміз, егер бұл кез-келген қайталануда массивтің кез-келген элементі [2-массивте] табылмаса, онда ол циклден шықпайды, 'j дегенді білдіреді 'мәні 1 массивтің ұзындығына тең [], біз 1 массивінде ұқсас элементтердің бірін таппадық дегенді білдіреді және біз жалған дегенді қайтарамыз, себебі ішкі жиын берілген жиынның барлық элементтерінен тұрады және біз таппадық бір.

код  

Жиым басқа массивтің ішкі жиыны екенін анықтау үшін C ++ коды

#include <iostream>
using namespace std;

bool isSubset(int arr1[], int arr2[], int l1, int l2)
{
    int i,j;
    for(i=0; i<l2; i++)
    {

        for(j=0; j<l1; j++)
        {
            if(arr2[i]==arr1[j])
                break;
        }
        if(j==l1)
            return false;
    }
    return true;
}
int main()
{
    int arr1[] = {1, 2, 3, 4, 5, 6};
    int arr2[] = {1, 3, 5};

    int l1=sizeof(arr1)/sizeof(arr1[0]);
    int l2=sizeof(arr2)/sizeof(arr2[0]);
    if(isSubset(arr1,arr2,l1,l2))
    {
        cout<<"arr2[] is a subset of arr1[]";
    }
    else
    {
        cout <<"arr2[] is not a subset of arr1[]"<<endl;
    }
    return 0;
}
arr2[] is a subset of arr1[]

Жиым басқа массивтің ішкі жиыны екенін анықтау үшін Java коды

class isArraySubset
{
    public static boolean isSubset(int arr1[],int arr2[], int l1, int l2)
    {
        int i = 0;
        int j = 0;
        for (i = 0; i < l2; i++)
        {
            for (j = 0; j < l1; j++)
            {
                if(arr2[i] == arr1[j])
                {
                    break;
                }
            }
            if (j == l1)
                return false;
        }
        return true;
    }
    public static void main(String args[])
    {
        int arr1[] = {1, 2, 3, 4, 5, 6};
        int arr2[] = {1, 3, 5};

        int l1 = arr1.length;
        int l2 = arr2.length;

        if(isSubset(arr1, arr2, l1, l2))
        {
            System.out.println("arr2[] is a subset of arr1[]");
        }
        else
        {
            System.out.println("arr2[] is not a subset of arr1[]");
        }
    }
}
arr2[] is a subset of arr1[]

Күрделілікті талдау  

Уақыттың күрделілігі

O (m * n) қайда «M» бұл arr1 және өлшемі «N» arr2 өлшемі. Біз уақыттың күрделілігін көпмүшелікке айналдырып, кірістірілген циклдарды қолдандық.

Сондай-ақ, қараңыз
Соманың максималды ұлғаюы

Ғарыштың күрделілігі

O (1), өйткені біз ешқандай қосымша массив / вектор қолданған жоқпыз.