पता लगाएं कि एक सरणी दूसरे सरणी का सबसेट है या नहीं


कठिनाई स्तर आसान
में अक्सर पूछा एकोलाइट जीई हेल्थकेयर क्वालकॉम
ऐरे द्विआधारी खोज हैश खोजना छंटाई

समस्या "ढूँढें कि क्या एक सरणी किसी अन्य सरणी का सबसेट है" बताता है कि आपको दो सरणियाँ दी गई हैं 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 array2 [] की लंबाई से कम है।
    1. जबकि j array1 [] की लंबाई से कम है।
      1. अगर गिरफ्तार 2 [i] गिरफ्तारी [j] के बराबर है, तो तोड़ दें।
  4. If j मी के बराबर है, असत्य पर लौटें।
  5. सच लौटा दो।

व्याख्या

हमारा काम यह पता लगाना है कि क्या सरणी दूसरा array1 का सबसेट है। तो हमारा मुख्य विचार नेस्टेड लूप का उपयोग करना और प्रत्येक तत्व की जांच करना है और array2 का प्रत्येक तत्व array1 में पाया जाता है, जिसका अर्थ है कि array2 array1 का सबसेट है।

हमें array1 और array2 में हमारे इनपुट के रूप में एक उदाहरण लेते हैं

उदाहरण

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

Array0 के 2 वें इंडेक्स के साथ शुरू, हम यह जांचने जा रहे हैं कि arrays0 के 2 वें इंडेक्स को array1 [i] में समान संख्या मिलती है या नहीं, और हां यह 11 के रूप में मिला है। इसलिए हम लूप को तोड़ने जा रहे हैं और i ++ करते हैं।

Array1 [] के 2 सूचकांक के साथ शुरू, हम यह जांचने जा रहे हैं कि arrays1 के 2 सूचकांक को array1 [i] में एक समान संख्या मिलती है या नहीं, और हां यह 3 के रूप में मिला है। इसलिए हम लूप को तोड़ने जा रहे हैं और i ++ ।

Array2 [] के 2 इंडेक्स के साथ शुरू, हम यह जांचने जा रहे हैं कि arrays2 के 2 इंडेक्स को array1 [i] में समान संख्या मिलती है या नहीं और यह 7 के रूप में पाया गया। इसलिए हम लूप को तोड़ने और i ++ करने जा रहे हैं।

Array1 [] के 2 सूचकांक के साथ शुरू, हम यह जांचने जा रहे हैं कि arrays1 के 2 सूचकांक को array1 [i] में समान संख्या मिलती है और 1 ने इसे पाया। इसलिए हम लूप को तोड़कर i ++ करने जा रहे हैं।

और अगर उस स्थिति के बारे में जिसे इस रूप में दर्शाया जाता है अगर (j = = m) इसका मतलब है, अगर किसी भी पुनरावृत्ति में अगर array2 का कोई तत्व array1 [] में नहीं पाया गया है, तो इसका मतलब है कि यह लूप से बाहर निकलता है बिना इसे तोड़ने का मतलब है 'j 'array1 की लंबाई के बराबर मान के साथ [] इसका मतलब है कि हमें array1 [] में समान तत्वों में से एक नहीं मिला है और हम झूठे हैं क्योंकि सबसेट में दिए गए सेट के सभी तत्व शामिल हैं और हमें नहीं मिला। एक।

कोड

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

जटिलता विश्लेषण

समय जटिलता

ओ (एम * एन) जहां "एम" arr1 का आकार है और "N" arr2 का आकार है। क्योंकि हमने नेस्टेड लूप्स का उपयोग किया है, जिससे समय जटिलता बहुपद बनती है।

अंतरिक्ष जटिलता

ओ (1), क्योंकि हमने किसी अतिरिक्त सरणी / वेक्टर का उपयोग नहीं किया है।