Намерете дали масивът е подмножество на друг масив


Ниво на трудност Лесно
Често задавани в Аколит GE Healthcare Qualcomm
Array Двоично търсене Хашиш Търсене сортиране

Проблемът „Намерете дали даден масив е подмножество на друг масив“ гласи, че са ви дадени два масива arra1 [] и array2 []. Дадените масиви са по несортиран начин. Вашата задача е да откриете дали array2 [] е подмножество на array1 [].

Пример

Намерете дали масивът е подмножество на друг масив

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, върнете false.
  5. Връщане вярно.

Обяснение

Нашата задача е да открием дали масив второто е подмножество на array1. Така че основната ни идея е да използваме вложения цикъл и да проверяваме всеки елемент и всеки елемент на array2 се намира в array1, което означава, че array2 е подмножество на array1.

Нека вземем пример като наш вход в array1 и array2

Пример

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

Започвайки с 0-ия индекс на array2, ще проверим дали 0-ият индекс на arrays2 намира подобно число в array1 [i] и да го намери като 11. Така че ще прекъснем цикъла и ще направим i ++.

Започвайки с 1-ви индекс на array2 [], ще проверим дали 1-ви индекс на arrays2 намира подобно число в array1 [i] и да го намери като 3. Така че ще прекъснем цикъла и направим i ++ .

Започвайки с 2-ри индекс на array2 [], ще проверим дали 2-ри индекс на arrays2 намира подобно число в array1 [i] и го е намерил като 7. Така че ще прекъснем цикъла и ще направим i ++.

Започвайки с 1-ви индекс на array2 [], ще проверим дали 1-ви индекс на масиви2 намира подобно число в array1 [i] и 1 го е намерил. Така че ще прекъснем цикъла и ще направим i ++.

А относно условието if, което е представено като if (j = = m), това означава, че в която и да е от итерациите, ако някой от елементите на array2 не е намерен в array1 [], означава, че излиза от цикъла, без да го прекъсва, означава „j 'със стойност, равна на дължината на масива1 [], което означава, че не намерихме нито един от елементите, подобни на масива1 [] и връщаме false, тъй като подмножеството се състои от целия елемент на дадения набор и не намерихме един.

код

Код на 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 и "н" е размерът на arr2. Тъй като сме използвали вложени цикли, правейки времевата сложност полином.

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

O (1), защото не сме използвали допълнителен масив / вектор.