ببینید آیا یک آرایه زیر مجموعه آرایه دیگری است یا خیر  


سطح دشواری ساده
اغلب در همبستگی GE بهداشت و درمان سامسونگ
صف جستجوی دودویی مخلوط جستجو مرتب سازی

مسئله "پیدا کردن اینکه آیا یک آرایه زیر مجموعه آرایه دیگری است" بیان می کند که دو آرایه 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 هر عنصری در array2 یافت می شود ، به این معنی که array1 یک زیر مجموعه از array2 است.

بیایید یک مثال به عنوان ورودی خود در array1 و array2 بگیریم

مثال

arr1 [] = {11 ، 1 ، 13 ، 21 ، 3 ، 7} ؛ arr2 [] = {11 ، 3 ، 7 ، 1}؛

با شروع از شاخص 0 آرایه 2 ، ما می خواهیم بررسی کنیم که آیا شاخص 0 آرایه ها عدد مشابهی را در آرایه 2 پیدا می کند [i] یا نه ، و بله آن را به عنوان 1 پیدا کرده است. بنابراین ما می خواهیم حلقه را بشکنیم و i ++ را انجام دهیم.

همچنین مشاهده کنید
طولانی ترین پیامد Bitonic

با شروع با شاخص اول آرایه 1 [] ، ما می خواهیم بررسی کنیم که آیا شاخص اول آرایه ها تعداد مشابهی را در آرایه 2 پیدا می کند [i] یا نه ، و بله آن را به عنوان 1 پیدا کرده است. بنابراین ما می خواهیم حلقه را بشکنیم و i ++ را انجام می دهیم .

با شروع با شاخص دوم آرایه 2 [] ، ما می خواهیم بررسی کنیم که آیا شاخص 2 آرایه ها عدد مشابهی را در آرایه 2 پیدا می کند [i] یا اینکه آن را به عنوان 2 پیدا کرده است. بنابراین ما می خواهیم حلقه را بشکنیم و i ++ را انجام دهیم.

با شروع با شاخص اول آرایه 1 [] ، ما می خواهیم بررسی کنیم که آیا شاخص اول آرایه ها تعداد مشابهی را در آرایه 2 پیدا می کند [i] و 1 آن را پیدا کرده است. بنابراین ما می خواهیم حلقه را بشکنیم و i ++ را انجام دهیم.

و در مورد شرط if که به صورت (j = = m) نشان داده می شود ، این بدان معناست که اگر در هر تکرار اگر عنصر آرایه 2 در آرایه 1 یافت نشود [] ، به این معنی است که بدون شکستن از حلقه خارج می شود به معنی 'j 'با مقداری برابر با طول آرایه 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[]

کد جاوا برای یافتن اینکه آیا یک آرایه زیر مجموعه آرایه دیگری است یا خیر

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) ، زیرا ما از هیچ آرایه / بردار اضافی استفاده نکرده ایم.