Bir massivin başqa bir massivin alt qrupu olub olmadığını tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit GE Healthcare Qualcomm
Geyim İkili axtarış Sükut Axtarış çeşidləyiciBaxılıb 27

“Bir massivin başqa bir massivin alt olub olmadığını tapın” problemi sizə iki arra1 [] və array2 [] massivlərinin verildiyini bildirir. Verilən massivlər çeşidlənməmiş şəkildədir. Taskınız, serialın [[] array2 [] alt dəsti olub olmadığını tapmaqdır.

misal

Bir massivin başqa bir massivin alt qrupu olub olmadığını tapınPin

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

Alqoritm

  1. İç içə döngəni açın.
  2. Məni 0-a, j-yə 0-a qoyun.
  3. Isə i massivin uzunluğundan azdır [].
    1. Isə j massivin uzunluğundan azdır [].
      1. Arr2 [i] arr [j] -ə bərabərdirsə, onda break.
  4. If j m-ə bərabərdir, yalnış qayıdır.
  5. Doğru qayıdın.

Izahat

Bizim vəzifəmiz, olub olmadığını tapmaqdır array ikincisi array1 alt hissəsidir. Beləliklə, əsas fikrimiz iç içə döngəni istifadə etmək və hər bir elementi yoxlamaqdır və array2-nin hər bir elementi array1-də tapılır, yəni array2 array1-in alt hissəsidir.

Array1 və array2-də giriş olaraq bir nümunə götürək

misal

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

Array0-nin 2-ci indeksindən başlayaraq arrays0-nin 2-ci indeksinin array1 [i] -də oxşar say tapıb-tapmadığını yoxlayacağıq və bəli onu 11 kimi tapdı. Beləliklə döngəni pozub i ++ edəcəyik.

Array1-nin 2-ci indeksindən başlayaraq [arrays1] -nin 2-ci indeksinin array1 [i] -də oxşar say tapıb-tapmadığını yoxlayacağıq və bəli 3 kimi tapdı. Beləliklə döngəni qırıb i ++ edəcəyik .

Array2-nin 2-ci indeksindən başlayaraq [], arrays2-nin 2-ci indeksinin array1 [i] -də oxşar say tapıb tapmadığını yoxlayacağıq və 7 kimi tapdı. Beləliklə döngəni qırıb i ++ edəcəyik.

Array1-nin 2-ci indeksindən başlayaraq [], array1-in 2-ci indeksinin array1 [i] -də oxşar say tapıb-tapmadığını yoxlayacağıq. Beləliklə, biz loopu pozacağıq və i ++ edirik.

Və əgər (j = = m) kimi təmsil olunan şərt bu deməkdirsə, təkrarlamanın hər hansı birində array2-in hər hansı bir elementi array1 [] -də tapılmadıqda, döngədən çıxdığı anlamına gəlir 'j 'serialın uzunluğuna bərabər bir qiymətlə [] serial 1-ə bənzər elementlərdən birini tapmadığımızı bildirir və yalnış qayıdırıq, çünki alt çoxluq verilən çoxluğun bütün elementlərindən ibarətdir və tapa bilmədik. bir.

Kodu

Bir cərgənin başqa bir sıra alt dəsti olub olmadığını tapmaq üçün C ++ kodu

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

Bir sıra başqa bir sıra alt dəsti olub olmadığını tapmaq üçün Java kodu

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ürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (m * n) hara "M" arr1 və ölçüsüdür "N" arr2 ölçüsüdür. Zaman mürəkkəbliyini polinom halına gətirərək iç içə döngələrdən istifadə etdik.

Kosmik Mürəkkəblik

O (1), çünki əlavə bir sıra / vektor istifadə etməmişik.

Translate »