معلوم کریں کہ کیا ایک صف دوسرے سرے کا سب سیٹ ہے


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے اکٹھا کرنا GE صحت کا خیال Qualcomm
لڑی ثنائی تلاش ہیش تلاش چھانٹ

مسئلہ "یہ تلاش کریں کہ کیا ایک صف کسی اور سرے کا سبسیٹ ہے" میں بتایا گیا ہے کہ آپ کو دو ارے ارا 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 ، j سے 0 پر سیٹ کریں۔
  3. جبکہ i صف کی لمبائی سے کم ہے [[]۔
    1. جبکہ j صف کی لمبائی سے کم ہے [[]۔
      1. اگر arr2 [i] برابر ہے [j] ، توڑو۔
  4. If j میٹر کے برابر ہے ، جھوٹا لوٹنا۔
  5. سچ لوٹنا۔

وضاحت

ہمارا کام یہ تلاش کرنا ہے کہ آیا صف دوسرا ارے 1 کا سب سیٹ ہے۔ لہذا ہمارا بنیادی خیال یہ ہے کہ گھریلو لوپ کو استعمال کریں اور ہر عنصر کو چیک کریں اور ارای 2 کا ہر عنصر سرنی 1 میں پایا جاتا ہے ، جس کا مطلب ہے کہ سرنی 2 ارے 1 کا سب سیٹ ہے۔

آئیے array1 اور array2 میں ہمارے ان پٹ کی حیثیت سے ایک مثال لیں

مثال کے طور پر

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

صف نمبر 0 کے 2 ویں انڈیکس کے ساتھ شروع کرتے ہوئے ، ہم یہ چیک کرنے جارہے ہیں کہ کیا ارای 0 کے 2 ویں انڈیکس میں ارے 1 [i] میں ایک جیسی تعداد مل گئی ہے ، اور ہاں اسے 11 کی طرح مل گیا ہے۔ لہذا ہم لوپ کو توڑنے جا رہے ہیں اور میں ++ کروں گا۔

ارای 1 کے پہلے اشاریہ کے ساتھ شروع ہو رہے ہیں [،] ہم یہ چیک کرنے جارہے ہیں کہ ارای 2 کا پہلا اشاریہ ارے 1 میں ایک ہی نمبر پاتا ہے [i] ، اور ہاں اس کو 2 مل گیا ہے۔ لہذا ہم لوپ کو توڑنے جا رہے ہیں اور میں ++ .

ارای 2 کے دوسرے انڈیکس کے ساتھ شروع کرتے ہوئے ، ہم یہ چیک کرنے جارہے ہیں کہ ارای 2 کا دوسرا انڈیکس ارے 2 میں اسی طرح کی تعداد تلاش کرتا ہے [i] اور اس نے اسے 2 پایا۔ لہذا ہم لوپ کو توڑنے جا رہے ہیں اور میں ++ کروں گا۔

ارای 1 کے پہلے اشاریہ کے ساتھ شروع ہو رہے ہیں [] ، ہم یہ چیک کرنے جارہے ہیں کہ ارای 2 کا پہلا انڈیکس ارے 1 [i] میں ایک ہی نمبر تلاش کرتا ہے اور 2 نے اسے پایا۔ تو ہم لوپ کو توڑنے جا رہے ہیں اور میں ++ کروں گا۔

اور اگر اس حالت کے بارے میں اگر اس کی نمائندگی کی گئی ہو گویا (j = = m) اس کا مطلب ہے ، اگر کسی بھی تکرار میں اگر صفی 2 کا عنصر صفی 1 میں نہیں پایا جاتا ہے [] ، اس کا مطلب ہے کہ یہ توڑے بغیر لوپ سے باہر آجاتا ہے تو اس کا مطلب ہے 'j 'سرنی 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[]

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (m * n) کہاں "ایم" arr1 اور کا سائز ہے "این" arr2 کا سائز ہے۔ چونکہ ہم نے گھماؤ والے لوپس کا استعمال کیا ہے ، وقت کی پیچیدگی کو متعدد بنا۔

خلائی پیچیدگی

O (1) ، کیونکہ ہم نے کوئی اضافی صف / ویکٹر استعمال نہیں کیا ہے۔