იპოვნეთ არის თუ არა მასივი სხვა მასივის ქვეჯგუფი


Რთული ტური Easy
ხშირად ეკითხებიან თანამოსაყრელი GE Healthcare Qualcomm
Array ორობითი ძებნა Hash Searching დახარისხება

პრობლემა "იპოვნეთ არის თუ არა მასივი სხვა მასივის ქვეჯგუფი" აცხადებს, რომ თქვენ გეძლევათ ორი მასივი arra1 [] და array2 []. მოცემული მასივები დალაგებულია. თქვენი ამოცანაა გაარკვიოთ არის თუ არა მასივი [[] array2 [].

მაგალითი

იპოვნეთ არის თუ არა მასივი სხვა მასივის ქვეჯგუფი

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] უდრის arr [j] - ს, მაშინ გატეხე.
  4. If j უდრის მ-ს, ცრუა.
  5. ნამდვილი დაბრუნება

განმარტება

ჩვენი ამოცანაა თუ არა მასივი მეორე არის მასივის 1 ქვეჯგუფი. ჩვენი მთავარი იდეა არის ჩადებული მარყუჟის გამოყენება და თითოეული ელემენტის შემოწმება და მასივი 2-ის ყოველი ელემენტი გვხვდება მასივში 1, რაც ნიშნავს, რომ მასივი 2 არის მასივის ქვესიმრავლე.

მოდით ავიღოთ მაგალითი, როგორც მასივი 1 და მასივი 2

მაგალითი

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

მასივის 0-ის ინდექსზე დაყრდნობით, ჩვენ ვაპირებთ შეამოწმოთ, არის თუ არა მასივების 2-ე ინდექსი მასივში [i] მსგავსი რიცხვი, და დიახ, იგი იპოვა, როგორც 0. ასე რომ, ჩვენ ვაპირებთ მარყუჟის გაწყვეტას და მე ვაკეთებ ++.

მასივის 1-ლი ინდექსიდან [], ჩვენ ვაპირებთ შეამოწმოთ, არის თუ არა მასივების 2-ე ინდექსი მასივში მსგავსი რიცხვი 1 [i], და დიახ, იგი იპოვნეს იგი როგორც 2. ასე რომ, ჩვენ ვაპირებთ მარყუჟის გაწყვეტას და მე ++ .

მასივის მე -2 ინდექსიდან დაწყებული [], ჩვენ ვაპირებთ შეამოწმოთ, არის თუ არა მასივების მე -2 ინდექსი მასივის მსგავსი [[i] მსგავსი რიცხვი და მიაგნო მას, როგორც 2. ასე რომ, ჩვენ ვაპირებთ მარყუჟის გაწყვეტას და მე ვაკეთებ i ++.

მასივის 1-ლი ინდექსიდან დაწყებული [], ჩვენ ვაპირებთ შეამოწმოთ, თუ მასივების 2-ლი ინდექსი იპოვა მსგავსი რიცხვი მასივში 1 [i] და 2 იპოვა იგი. ჩვენ ვაპირებთ მარყუჟის გატეხვას და მე ++

ხოლო თუ პირობა, რომელიც წარმოდგენილია, როგორც (j = = m), ეს ნიშნავს, თუ რომელიმე გამეორებაში, თუ array2- ის რომელიმე ელემენტი არ არის ნაპოვნი მასივში 1 [], ნიშნავს რომ ის გამოდის მარყუჟიდან გაწყვეტის გარეშე, ეს ნიშნავს 'j 'მასივის სიგრძის ტოლი მნიშვნელობით 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 (მ * ნ) სადაც "მ" არის arr1- ის ზომა და "ნ" არის arr2- ის ზომა. იმის გამო, რომ ჩვენ გამოვიყენეთ ჩასმული მარყუჟები, რაც დროის სირთულეს პოლინომია.

სივრცის სირთულე

O (1), რადგან ჩვენ არ გამოვიყენეთ რაიმე დამატებითი მასივი / ვექტორი.