Пронађите да ли је низ подскуп другог низа  


Ниво тешкоће Лако
Често питани у Аццолите ГЕ Хеалтхцаре куалцомм
Ред Бинарна претрага Хасх Претраживање сортирање

Проблем „Пронађи да ли је низ подскуп другог низа“ наводи да су вам дата два низа арра1 [] и арраи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 [].

Алгоритам  

  1. Отворите угнежђену петљу.
  2. Подесите и на 0, ј на 0.
  3. Док i је мања од дужине низа2 [].
    1. Док j је мања од дужине низа1 [].
      1. Ако је арр2 [и] једнако арр [ј], онда прекини.
  4. If j је једнако м, врати фалсе.
  5. Повратак истинит.

Објашњење

Наш задатак је да утврдимо да ли поредак друго је подскуп низа1. Дакле, наша главна идеја је да користимо угнежђену петљу и проверимо сваки елемент и сваки низ арраи2 се налази у арраи1, што значи да је арраи2 подскуп арраи1.

Узмимо пример као наш улаз у арраи1 и арраи2

Пример

арр1 [] = {11, 1, 13, 21, 3, 7}; арр2 [] = {11, 3, 7, 1};

Почевши од 0. индекса низа2, проверићемо да ли 0. индекс низова2 проналази сличан број у низу1 [и], и да га је пронашао као 11. Дакле, прекинућемо петљу и урадити и ++.

Види такође
Најдужа битонска след

Почевши од првог индекса низа1 [], проверићемо да ли 2. индекс низова1 проналази сличан број у низу2 [и], и да га је пронашао као 1. Дакле, прекинут ћемо петљу и урадити и ++ .

Почевши од другог индекса низа2 [], проверићемо да ли други индекс низова2 проналази сличан број у низу2 [и] и нашао га је као 2. Дакле, прекинут ћемо петљу и урадити и ++.

Почевши од првог индекса низа1 [], проверићемо да ли 2. индекс низова1 проналази сличан број у низу2 [и] и 1 га је пронашао. Прекинућемо петљу и урадити и ++.

А отприлике ако услов који је представљен као да је (ј = = м) то значи, ако у било којој од итерација ако било који елемент низа2 није пронађен у низу1 [], значи да излази из петље без прекида, значи 'ј 'са вредношћу једнаком дужини низа1 [] што значи да нисмо пронашли један од елемената сличних низу1 [] и враћамо фалсе јер се подскуп састоји од целог елемента датог скупа и нисмо пронашли једно.

код  

Ц ++ код да би се утврдило да ли је низ подскуп другог низа

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

Јава код да би се утврдило да ли је низ подскуп другог низа

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

Анализа сложености  

Сложеност времена

О (м * н) где "М" је величина арр1 и „Н“ је величина арр2. Зато што смо користили угнежђене петље, чинећи временску сложеност полиномом.

Види такође
Максимална сума која се повећава

Сложеност простора

О (1), јер нисмо користили додатни низ / вектор.