අරාව වෙනත් අරාවක උප කුලකයක් දැයි සොයා ගන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇසොලයිට් GE සෞඛ්යාරක්ෂණය 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. 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 වන දර්ශකය අරාව 1 [i] හි සමාන සංඛ්‍යාවක් සොයාගෙන XNUMX ක් සොයා ගත්තේද යන්න අපි පරීක්ෂා කරන්නෙමු. ඉතින් අපි ලූප් එක කඩලා i ++ කරන්න යනවා.

(J = = m) ලෙස නිරූපණය වන කොන්දේසියක් නම්, මෙයින් අදහස් කරන්නේ, කිසියම් පුනරාවර්තනයක් තුළ අරාව 2 හි කිසියම් මූලද්‍රව්‍යයක් අරාව 1 [] හි සොයාගත නොහැකි නම්, එයින් අදහස් වන්නේ එය බිඳී නොගෙන ලූපයෙන් පිටතට එන බවයි. 'අරාව 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[]

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එම් * එන්) එහිදී "එම්" arr1 සහ “N” arr2 හි ප්‍රමාණයයි. මන්දයත් අප කැදැලි වළළු භාවිතා කර ඇති අතර කාලය සංකීර්ණ බහුපද බවට පත් කර ඇත.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), අපි අතිරේක අරා / දෛශික භාවිතා කර නැති නිසා.