አንድ ድርድር የሌላ ድርድር ንዑስ መሆኑን ይፈልጉ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ GE የጤና Qualcomm
ሰልፍ የሁለትዮሽ ፍለጋ ሃሽ በመፈለግ ላይ መደርደር

ችግሩ “አንድ ድርድር የሌላ ድርድር ንዑስ ክፍል መሆኑን ይፈልጉ” የሚለው ሁለት ድርድር arra1 [] እና ድርድር 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 ከድርድር ርዝመት ያነሰ ነው 2 []።
    1. ቢሆንም j ከድርድር ርዝመት ያነሰ ነው 1 []።
      1. Arr2 [i] ከአራር [j] ጋር እኩል ከሆነ ፣ ከዚያ ይሰብሩ።
  4. If j ከ m ጋር እኩል ነው ፣ ሐሰትን ይመልሱ ፡፡
  5. ወደ እውነት ተመለስ

ማስረጃ

የእኛ ተግባር እ.ኤ.አ. ደርድር ሁለተኛው የአንድ ድርድር ንዑስ ክፍል 1 ነው። ስለዚህ ዋናው ሀሳባችን የጎጆውን ሉፕ መጠቀም እና እያንዳንዱን ንጥረ ነገር መፈተሽ እና የድርጅት 2 እያንዳንዱ ንጥረ ነገር በድርድር ውስጥ ይገኛል ፣ ይህም ማለት ድርድር 1 ንዑስ ክፍል 2 ነው ማለት ነው።

በድርድር 1 እና በድርድር 2 ውስጥ እንደ ግብዓታችን ምሳሌ እንውሰድ

ለምሳሌ

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

ከድርድር 0 ኛ 2 ኛ ማውጫ ጀምሮ የ 0 ኛ ድርድር ኢንዴክስ በድርድር 2 [i] ውስጥ ተመሳሳይ ቁጥር ያለው መሆኑን እናረጋግጣለን ፣ እና አዎ እንደ 1 አገኘነው ስለዚህ እኛ ጉበቱን ሰብረን እና እኔ ++ ን እናደርጋለን ፡፡

ተመልከት
ረጅሙ የቢቶኒክ ተከታይ

ከድርጅት 1 ኛ ማውጫ (2) ጀምሮ ፣ የ 1 ኛ ድርድር 2 ኢንዴክስ በድርድር 1 [i] ውስጥ ተመሳሳይ ቁጥር ያለው መሆኑን እናረጋግጣለን ፣ እና አዎ እንደ 3. አግኝቷል ፡፡ .

ከድርድር 2 [] 2 ኛ ማውጫ ጀምሮ ፣ የ 2 ኛ ድርድር መረጃ ጠቋሚ በድርድር 2 [i] ውስጥ ተመሳሳይ ቁጥር ያለው መሆኑን እናረጋግጣለን እንሄዳለን ፣ ስለሆነም ደፍረን አፍርሰን 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[]

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (m * n) የት "M" የ arr1 መጠን እና ነው “N” የ arr2 መጠን ነው። ምክንያቱም እኛ የሰፈነውን ቀለበቶች ስለተጠቀምን ፣ ጊዜውን ውስብስብነት ፖሊኖሚያል ያደርገዋል ፡፡

ተመልከት
ከፍተኛው ድምር ቀጣይ ውጤት

የቦታ ውስብስብነት

ኦ (1) ፣ ምክንያቱም ምንም ተጨማሪ ድርድር / ቬክተር አልተጠቀምንም።