অ্যারে অন্য অ্যারের সাবসেট কিনা তা সন্ধান করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি জিই হেলথকেয়ার কোয়ালকম
বিন্যাস বাইনারি অনুসন্ধান কাটা খোঁজ শ্রেণীবিভাজন

সমস্যাটি "একটি অ্যারে অন্য অ্যারের উপসেট কিনা তা সন্ধান করুন" বলে উল্লেখ করে যে আপনাকে দুটি অ্যারে অ্যারে 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. I তে 0, j থেকে 0 তে সেট করুন।
  3. যদিও i অ্যারে 2 এর দৈর্ঘ্যের চেয়ে কম []।
    1. যদিও j অ্যারে 1 এর দৈর্ঘ্যের চেয়ে কম []।
      1. যদি arr2 [i] সমান তীর [j] হয় তবে বিরতি দিন।
  4. If j মিটার সমান, মিথ্যা প্রত্যাবর্তন।
  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 তে একই সংখ্যা খুঁজে পেয়েছে [i], এবং হ্যাঁ এটি 1 হিসাবে পাওয়া গেছে তাই আমরা লুপটি ভেঙে যাচ্ছি এবং আমি ++ করব ।

অ্যারে 2 এর দ্বিতীয় সূচক [] এর সাথে শুরু করে, আমরা পরীক্ষা করতে যাচ্ছি যে অ্যারে 2 এর 2 তম সূচকটি অ্যারে 2 তে একই সংখ্যা খুঁজে পেয়েছে এবং [এটি] এটি 1 হিসাবে পাওয়া গেছে। সুতরাং আমরা লুপটি ভেঙে চলেছি এবং আমি ++ করব।

অ্যারে 1 এর প্রথম সূচক [] এর সাথে শুরু করে, আমরা পরীক্ষা করতে যাচ্ছি যে অ্যারে 2 এর 1 ম সূচকটি অ্যারে 2 [i] এবং 1 টিতে এটি খুঁজে পেয়েছে কিনা similar সুতরাং আমরা লুপটি ভাঙ্গতে যাচ্ছি এবং আমি ++ করব।

এবং যদি শর্তটি প্রতিনিধিত্ব করা হয় যা যদি (জে = = মি) এর অর্থ হয় তবে এর পুনরাবৃত্তির মধ্যে যদি অ্যারে 2 এর কোনও উপাদান অ্যারে 1 [] তে পাওয়া যায় না, এর অর্থ এটি ভাঙ্গা ছাড়াই লুপ থেকে বেরিয়ে আসে যার অর্থ 'জে 'অ্যারে 1 এর দৈর্ঘ্যের সমান মানের সাথে [] এর অর্থ আমরা অ্যারে 1 তে অনুরূপ উপাদানগুলির মধ্যে একটিও পাইনি এবং আমরা মিথ্যা প্রত্যাবর্তন করি কারণ উপসেটটি প্রদত্ত সংস্থার সমস্ত উপাদানকে ধারণ করে এবং আমরা খুঁজে পাইনি we এক.

কোড

অ্যারে অন্য অ্যারের সাবসেট কিনা তা সন্ধান করতে সি ++ কোড

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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এম * এন) কোথায় "M" এআর 1 এর আকার এবং "এন" এআর 2 এর আকার। কারণ আমরা নেস্টেড লুপগুলি ব্যবহার করেছি, সময়কে জটিলতা বহুপদী করে তুলছি।

স্পেস জটিলতা ity

ও (1), কারণ আমরা কোনও অতিরিক্ত অ্যারে / ভেক্টর ব্যবহার করি নি।