Массив башка массивдин топтому экендигин табуу


Кыйынчылык деңгээли жеңил
Көп суралган Accolite GE Саламаттыкты сактоо Qualcomm
согуштук тизме Binary Search таштанды издөө сорттоо

"Массивдин башка массивдин топтому экендигин табуу" маселеси сизге arra1 [] жана массив2 [] деген эки массив берилгенин билдирет. Берилген массивдер иреттелген эмес тартипте. Сиздин милдетиңиз - массив2 [] массивдин [[1] кичи бөлүгү экендигин табуу.

мисал

Массив башка массивдин топтому экендигин табуу

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 [].

Algorithm

  1. Уяланган циклди ачыңыз.
  2. I ден 0, j ден 0 ге чейин коюңуз.
  3. жатканда i массивинин узундугунан аз [].
    1. жатканда j массивинин узундугунан аз [].
      1. Arr2 [i] arr [j] га барабар болсо, анда break.
  4. If j мге барабар, жалган деп кайтарыңыз.
  5. Чындыкты кайтаруу.

түшүндүрүү

Биздин милдет - же жок экендигин табуу согуштук тизме экинчиси - 1-массивдин топтому. Ошентип, биздин негизги идеябыз - камтылган циклди колдонуу жана ар бир элементти текшерүү жана array2дин ар бир элементи array1 ден табылат, демек array2 массивдин 1 топтому.

Массив1 жана массив2деги киришибиз катары мисал алалы

мисал

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

Массив0дин 2-көрсөткүчүнөн баштап, Массив0дин 2-көрсөткүчү [1] массивинде окшош санды тапкандыгын текшерип, ооба, аны 11 деп тапты. Ошентип, биз циклди бузуп, i ++ кылабыз.

Массивдин 1-көрсөткүчүнөн [] баштап, массивдин 2 индекси 1 массивинде [i] окшош санды тапкандыгын текшерип, ооба, аны 2 деп тапты. Ошентип, циклди бузуп, i ++ кылабыз .

Массив2дин 2-индексинен баштап, [2] массивдин 2-көрсөткүчү [1] массивинде окшош санды тапкандыгын текшерип, аны 7 деп тапты. Ошентип, циклди бузуп, 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) кайда "М" arr1 жана өлчөмү "N" arr2 өлчөмү. Себеби биз убакыттын татаалдыгын көп мүчөлүү кылып, уяланган циклдерди колдондук.

Космостун татаалдыгы

O (1), анткени биз эч кандай кошумча массив / вектор колдонгон эмеспиз.