រកមើលថាតើអារេជាសំណុំរងនៃអារេផ្សេងទៀត


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ គួរឱ្យគោរព ក្រុមហ៊ុន GE សុខភាព ក្រុមហ៊ុន qualcomm
អារេ ការស្វែងរកគោលពីរ ហាស់ ការស្វែងរក តម្រៀប

បញ្ហា“ រកថាតើអារេមួយដែលជាសំណុំរងនៃអារេមួយផ្សេងទៀត” ចែងថាអ្នកត្រូវបានផ្តល់អារេ ១ [] និងអារេ ២ [] ។ អារេដែលបានផ្តល់ឱ្យគឺនៅក្នុងលក្ខណៈដែលមិនបានតម្រៀប។ ភារកិច្ចរបស់អ្នកគឺត្រូវស្វែងរកថាតើអារេ ២ [] ជាសំណុំរងនៃអារេ ១ [] ។

ឧទាហរណ៍

រកមើលថាតើអារេជាសំណុំរងនៃអារេផ្សេងទៀត

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. កំណត់អាយទៅ ០, ចាដល់ ០ ។
  3. ខណៈពេល i គឺតិចជាងប្រវែងអារេ ២ [] ។
    1. ខណៈពេល j គឺតិចជាងប្រវែងអារេ ២ [] ។
      1. ប្រសិនបើ arr2 [ខ្ញុំ] ស្មើនឹងការមកដល់ [j] បន្ទាប់មកបំបែក។
  4. If j ស្មើនឹង m, ត្រឡប់មិនពិត។
  5. ត្រឡប់ពិត។

ការពន្យល់

ភារកិច្ចរបស់យើងគឺត្រូវរកមើលថាតើ អារេ ទីពីរគឺជាសំណុំរងនៃអារេ ១ ។ ដូច្នេះគំនិតចម្បងរបស់យើងគឺត្រូវប្រើរង្វិលជុំដែលនៅជាសំបុកហើយពិនិត្យមើលធាតុនីមួយៗនិងអារេទី ២ នៃធាតុទាំងអស់ត្រូវបានរកឃើញនៅក្នុងអារេ ១ ដែលមានន័យថាអារេ ២ គឺជាសំណុំរងនៃអារេ ១ ។

ចូរយើងយកឧទាហរណ៍មួយជាការបញ្ចូលរបស់យើងនៅក្នុងអារេ ១ និងអារេ ២

ឧទាហរណ៍

មកដល់ ១ [] = {១១, ១, ១៣, ២១, ៣, ៧}; arr1 [] = {១១, ៣, ៧, ១};

ចាប់ផ្តើមជាមួយសន្ទស្សន៍ទី ០ នៃអារេ ២ យើងនឹងពិនិត្យមើលថាតើសន្ទស្សន៍លេខ ០ នៃអារេ ២ រកឃើញលេខស្រដៀងគ្នានៅក្នុងជួរ ១ [i] ហើយមែនវារកឃើញថាវាជាលេខ ១១ ។ ដូច្នេះយើងនឹងបំបែករង្វិលជុំហើយធ្វើ i ++ ។

ចាប់ផ្តើមជាមួយសន្ទស្សន៍ទី ១ នៃអារេ ២ [] យើងនឹងពិនិត្យមើលថាតើសន្ទស្សន៍ទី ១ នៃអារេ ២ រកឃើញលេខស្រដៀងគ្នានៅក្នុងជួរ ១ [ខ្ញុំ] ហើយមែនវាបានរកឃើញថាវាជាលេខ ៣ ។ ដូច្នេះយើងនឹងបំបែករង្វិលជុំហើយធ្វើ i ++ ។ ។

ចាប់ផ្តើមជាមួយសន្ទស្សន៍ទី ២ នៃអារេ ២ [] យើងនឹងពិនិត្យមើលថាតើសន្ទស្សន៍ទី ២ នៃអារេ ២ រកឃើញលេខស្រដៀងគ្នានៅក្នុងជួរ ១ [i] ហើយវាបានរកឃើញថាវាជាលេខ ៧ ដូច្នេះយើងនឹងបំបែករង្វិលជុំហើយធ្វើ i ++ ។

ចាប់ផ្តើមជាមួយសន្ទស្សន៍ទី ១ នៃអារេ ២ [] យើងនឹងពិនិត្យមើលថាតើសន្ទស្សន៍ទី ១ នៃអារេ ២ រកឃើញលេខស្រដៀងគ្នានៅក្នុងជួរ ១ [i] ហើយ ១ បានរកឃើញទេ។ ដូច្នេះយើងនឹងបំបែករង្វិលជុំហើយធ្វើ i ++ ។

ហើយប្រសិនបើលក្ខខណ្ឌដែលត្រូវបានតំណាងដូចជា (j = = m) នេះមានន័យថាប្រសិនបើនៅក្នុងការឆ្លើយតបណាមួយនៃធាតុរបស់អារេ ២ មិនត្រូវបានរកឃើញនៅក្នុងអារេ ១ [] មានន័យថាវាចេញពីរង្វិលជុំដោយមិនបំបែកវាមានន័យថា 'j 'ជាមួយតំលៃស្មើនឹងប្រវែងអារេ ១ ដែលមានន័យថាយើងរកមិនឃើញធាតុស្រដៀងគ្នាក្នុងអារេ ១ ទេហើយយើងត្រឡប់មិនពិតពីព្រោះសំណុំរងមានធាតុទាំងអស់នៃសំណុំដែលបានផ្តល់ហើយយើងរកមិនឃើញ មួយ។

លេខកូដ

កូដ 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 (m * n) ដែលជាកន្លែងដែល "m" គឺជាទំហំរបស់ arr1 និង “ n” គឺជាទំហំរបស់ arr2 ។ ដោយសារតែយើងបានប្រើរង្វិលជុំដែលមានសំណាញ់ធ្វើឱ្យពេលវេលាមានភាពស្មុគស្មាញ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ពីព្រោះយើងមិនបានប្រើអារេ / វ៉ិចទ័របន្ថែមទេ។