अ‍ॅरे दुसर्‍या अ‍ॅरेचा सबसेट आहे की नाही ते शोधा


अडचण पातळी सोपे
वारंवार विचारले एकत्रित जीई हेल्थकेअर 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 ते 0, j ते XNUMX सेट करा.
  3. तर i अ‍ॅरे 2 च्या लांबीपेक्षा कमी आहे [].
    1. तर j अ‍ॅरे 1 च्या लांबीपेक्षा कमी आहे [].
      1. जर एर 2 [i] बरोबर अरर [जे] असेल तर ब्रेक करा.
  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 मध्ये शोधला आहे की नाही हे तपासणार आहोत [i] आणि त्यास ते 1 आढळले तर आपण लूप तोडून आय ++ करणार आहोत.

अ‍ॅरे 1 च्या पहिल्या अनुक्रमणिका [] सह प्रारंभ करून, आम्ही एरे 2 मधील 1 ला अनुक्रमणिका अ‍ॅरे 2 [i] आणि 1 मध्ये सापडली की नाही हे तपासणार आहोत. म्हणून आपण लूप तोडून आपण ++ करणार आहोत.

आणि जर अशी स्थिती जी (j = = m) असे दर्शविली गेली असेल तर याचा अर्थ असा आहे की जर एखाद्या पुनरावृत्तीमध्ये जर अ‍ॅरे 2 मधील कोणताही घटक अ‍ॅरे 1 मध्ये आढळला नसेल तर [म्हणजे, तो तोडल्याशिवाय लूपमधून बाहेर पडतो म्हणजे 'जे' 'अ‍ॅरे 1 च्या लांबीच्या समान मूल्यासह [] याचा अर्थ असा आहे की आम्हाला अ‍ॅरे 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[]

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एम * एन) जेथे "M" एआर 1 आणि चा आकार आहे “एन” एआर 2 चा आकार आहे. कारण आम्ही नेस्टेड लूप वापरल्या आहेत, ज्यामुळे वेळ गुंतागुंत बहुपदी बनते.

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण आम्ही कोणताही अतिरिक्त अ‍ॅरे / वेक्टर वापरलेला नाही.