Пронајдете дали низата е подмножество на друга низа  


Ниво на тешкотија Лесно
Често прашувано во Аколит ГЕ здравство Квалком
Низа Бинарно пребарување Хаш Пребарување Сортирање

Проблемот „Пронајдете дали низата е подмножество на друга низа“ вели дека ви се дадени две низи arra1 [] и array2 []. Дадените низи се на несортиран начин. Ваша задача е да откриете дали низата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. Поставете i на 0, j на 0.
  3. Додека i е помала од должината на низата2 [].
    1. Додека j е помала од должината на низата1 [].
      1. Ако arr2 [i] е еднакво на arr [j], тогаш скрши.
  4. If j е еднакво на m, врати неточно.
  5. Врати се вистинито.

Објаснување

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

Дозволете ни да земеме пример како наш влез во низата1 и низата2

пример

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

Почнувајќи од 0-от индекс на низа2, ќе провериме дали 0-от индекс на низи2 наоѓа сличен број во низата1 [i], и да го најде како 11. Значи, ќе ја разбиеме јамката и ќе направиме ++.

Видете исто така
Најдолга битоничка последица

Почнувајќи со 1-ви индекс на низа2 [], ќе провериме дали 1-виот индекс на низи2 наоѓа сличен број во низата1 [i], и да го најде како 3. Значи, ќе ја разбиеме јамката и ќе направам ++ .

Почнувајќи со 2-риот индекс на низата2 [], ќе провериме дали 2-от индекс на низи2 наоѓа сличен број во низата1 [i] и го најде како 7. Значи, ќе ја разбиеме јамката и ќе направиме ++.

Почнувајќи со 1-ви индекс на низа2 [], ќе провериме дали 1-виот индекс на низи2 наоѓа сличен број во низата1 [i] и 1 го најде. Значи, ние ќе ја прекинеме јамката и ќе направиме ++.

И за тоа дали услов што е претставен како да е (j = = m) ова значи, ако во кое било повторување ако некој од елементите на низата2 не се најде во низата1 [], значи дека излегува од јамката без да се скрши тоа значи '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[]

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

Временска комплексност

О (м * н) каде "M" е големината на arr1 и „Н“ е големината на arr2. Бидејќи користевме вгнездени јамки, со што сложеноста на времето е полином.

Видете исто така
Максимална сума што ја зголемува последицата

Комплексноста на просторот

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