శ్రేణి మరొక శ్రేణి యొక్క ఉపసమితి కాదా అని కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అకోలైట్ GE హెల్త్ క్వాల్కమ్
అర్రే బైనరీ శోధన హాష్ శోధించండి సార్టింగ్

“శ్రేణి మరొక శ్రేణి యొక్క ఉపసమితి కాదా అని కనుగొనండి” అనే సమస్య మీకు రెండు శ్రేణుల శ్రేణి 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] arr [j] కు సమానం అయితే, విచ్ఛిన్నం.
  4. If j m కు సమానం, తప్పుడు తిరిగి.
  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 గా కనుగొనబడింది. కాబట్టి మనం లూప్‌ను విచ్ఛిన్నం చేసి i ++ చేయబోతున్నాం.

శ్రేణి 1 యొక్క 2 వ సూచికతో ప్రారంభించి, శ్రేణుల 1 యొక్క 2 వ సూచిక శ్రేణి 1 [i] లో ఇలాంటి సంఖ్యను కనుగొంటుందో లేదో మేము తనిఖీ చేయబోతున్నాము మరియు అవును అది 3 గా కనుగొనబడింది. కాబట్టి మనం లూప్‌ను విచ్ఛిన్నం చేసి i ++ చేయబోతున్నాం .

శ్రేణి 2 యొక్క 2 వ సూచికతో ప్రారంభించి, శ్రేణుల 2 యొక్క 2 వ సూచిక శ్రేణి 1 [i] లో ఇలాంటి సంఖ్యను కనుగొంటుందో లేదో తనిఖీ చేయబోతున్నాము మరియు అది 7 గా కనుగొనబడింది. కాబట్టి మనం లూప్‌ను విచ్ఛిన్నం చేసి i ++ చేయబోతున్నాం.

శ్రేణి 1 యొక్క 2 వ సూచికతో ప్రారంభించి, శ్రేణుల 1 యొక్క 2 వ సూచిక శ్రేణి 1 [i] లో ఇలాంటి సంఖ్యను కనుగొంటుందో లేదో తనిఖీ చేయబోతున్నాము మరియు 1 దానిని కనుగొన్నాము. కాబట్టి మనం లూప్ ను విచ్ఛిన్నం చేసి i ++ చేయబోతున్నాం.

(J = = m) వలె ప్రాతినిధ్యం వహిస్తున్న షరతు గురించి దీని అర్థం, ఏదైనా పునరావృతంలో అర్రే 2 యొక్క మూలకం అర్రే 1 [] లో కనుగొనబడకపోతే, అది విచ్ఛిన్నం చేయకుండా లూప్ నుండి బయటకు వస్తుంది అంటే 'j 'శ్రేణి 1 యొక్క పొడవుకు సమానమైన విలువతో [] అంటే అర్రే 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 (మ * n) (ఇక్కడ "M" arr1 యొక్క పరిమాణం మరియు “N” arr2 యొక్క పరిమాణం. ఎందుకంటే మేము సమూహ ఉచ్చులను ఉపయోగించాము, సమయ సంక్లిష్టతను బహుపది.

అంతరిక్ష సంక్లిష్టత

ఓ (1), ఎందుకంటే మేము అదనపు శ్రేణి / వెక్టర్‌ను ఉపయోగించలేదు.