Рубрики

Найти, является ли массив подмножеством другого массива | Добавлен метод 3

Даны два массива: arr1 [0..m-1] и arr2 [0..n-1]. Найдите, является ли arr2 [] подмножеством arr1 [] или нет. Оба массива не в отсортированном порядке. Можно предположить, что элементы в обоих массивах различны.

Примеры:

Input: arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1}
Output: arr2[] is a subset of arr1[]

Input: arr1[] = {1, 2, 3, 4, 5, 6}, arr2[] = {1, 2, 4}
Output: arr2[] is a subset of arr1[]

Input: arr1[] = {10, 5, 2, 23, 19}, arr2[] = {19, 5, 3}
Output: arr2[] is not a subset of arr1[]

Способ 1 (простой) :
Используйте два цикла: внешний цикл выбирает все элементы arr2 [] один за другим. Внутренний цикл линейно ищет элемент, выбранный внешним циклом. Если все элементы найдены, вернуть 1, иначе вернуть 0.

C ++

// C ++ программа, чтобы найти ли массив
// это подмножество другого массива
#include<bits/stdc++.h>

  
/ * Вернуть 1, если arr2 [] является подмножеством
arr1 [] * /

bool isSubset(int arr1[], int arr2[], 

                        int m, int n)

{

    int i = 0;

    int j = 0;

    for (i = 0; i < n; i++)

    {

        for (j = 0; j < m; j++)

        {

            if(arr2[i] == arr1[j])

                break;

        }

          

        / * Если вышеуказанный внутренний цикл был

        не сломан тогда arr2 [i]

        отсутствует в arr1 [] * /

        if (j == m)

            return 0;

    }

      

    / * Если мы доберемся сюда, то все

    присутствуют элементы arr2 []

    в arr1 [] * /

    return 1;

}

  
// Код драйвера

int main()

{

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

    int arr2[] = {11, 3, 7, 1};

  

    int m = sizeof(arr1)/sizeof(arr1[0]);

    int n = sizeof(arr2)/sizeof(arr2[0]);

  

    if(isSubset(arr1, arr2, m, n))

        printf("arr2[] is subset of arr1[] ");

    else

        printf("arr2[] is not a subset of arr1[]");     

  

    getchar();

    return 0;

}

Джава

// Java-программа для определения наличия массива
// это подмножество другого массива

  

class GFG {

  

    / * Вернуть true, если arr2 [] является подмножеством

    из arr1 [] * /

    static boolean isSubset(int arr1[], 

                int arr2[], int m, int n)

    {

        int i = 0;

        int j = 0;

        for (i = 0; i < n; i++)

        {

            for (j = 0; j < m; j++)

                if(arr2[i] == arr1[j])

                    break;

              

            / * Если вышеуказанный внутренний цикл

            не был сломан вообще тогда

            arr2 [i] отсутствует в

            arr1 [] * /

            if (j == m)

                return false;

        }

          

        / * Если мы доберемся сюда, то все

        присутствуют элементы arr2 []

        в arr1 [] * /

        return true;

    }

      

    // Код драйвера

    public static void main(String args[])

    {

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

        int arr2[] = {11, 3, 7, 1};

          

        int m = arr1.length;

        int n = arr2.length;

      

        if(isSubset(arr1, arr2, m, n))

            System.out.print("arr2[] is "

                  + "subset of arr1[] ");

        else

            System.out.print("arr2[] is "

             + "not a subset of arr1[]"); 

    }

}

Python 3

# Python 3 программа для определения наличия массива
# является подмножеством другого массива

  
# Вернуть 1, если arr2 [] является подмножеством
# arr1 []

def isSubset(arr1, arr2, m, n):

    i = 0

    j = 0

    for i in range(n):

        for j in range(m):

            if(arr2[i] == arr1[j]):

                break

          

        # Если вышеуказанный внутренний цикл был

        # не сломан вообще тогда arr2 [i]

        # отсутствует в arr1 []

        if (j == m):

            return 0

      

    # Если мы доберемся сюда, то все

    # присутствуют элементы arr2 []

    # в arr1 []

    return 1

  
# Код драйвера

if __name__ == "__main__":

      

    arr1 = [11, 1, 13, 21, 3, 7]

    arr2 = [11, 3, 7, 1]

  

    m = len(arr1)

    n = len(arr2)

  

    if(isSubset(arr1, arr2, m, n)):

        print("arr2[] is subset of arr1[] ")

    else:

        print("arr2[] is not a subset of arr1[]")

  
# Этот код предоставлен ita_c

C #

// C # программа, чтобы найти ли массив
// это подмножество другого массива

using System;

  

class GFG {

  

    / * Вернуть true, если arr2 [] является

    подмножество arr1 [] * /

    static bool isSubset(int []arr1, 

               int []arr2, int m, int n)

    {

        int i = 0;

        int j = 0;

        for (i = 0; i < n; i++)

        {

            for (j = 0; j < m; j++)

                if(arr2[i] == arr1[j])

                    break;

              

            / * Если вышеуказанный внутренний цикл

            не был сломан вообще тогда

            arr2 [i] отсутствует в

            arr1 [] * /

            if (j == m)

                return false;

        }

          

        / * Если мы доберемся сюда, то все

        присутствуют элементы arr2 []

        в arr1 [] * /

        return true;

    }

      

    // Функция драйвера

    public static void Main()

    {

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

        int []arr2 = {11, 3, 7, 1};

          

        int m = arr1.Length;

        int n = arr2.Length;

      

        if(isSubset(arr1, arr2, m, n))

        Console.WriteLine("arr2[] is subset"

                           + " of arr1[] ");

        else

        Console.WriteLine("arr2[] is not a "

                      + "subset of arr1[]");

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP-программа для определения наличия массива
// это подмножество другого массива

  
/ * Вернуть 1, если arr2 [] является подмножеством
arr1 [] * /

function isSubset($arr1, $arr2, $m, $n)

{

    $i = 0;

    $j = 0;

    for ($i = 0; $i < $n; $i++)

    {

        for ($j = 0; $j < $m; $j++)

        {

            if($arr2[$i] == $arr1[$j])

                break;

        }

          

        / * Если вышеуказанный внутренний цикл был

        не сломан тогда arr2 [i]

        отсутствует в arr1 [] * /

        if ($j == $m)

            return 0;

    }

      

    / * Если мы доберемся сюда, то все

    присутствуют элементы arr2 []

    в arr1 [] * /

    return 1;

}

  
// Код драйвера

    $arr1 = array(11, 1, 13, 21, 3, 7);

    $arr2 = array(11, 3, 7, 1);

  

    $m = count($arr1);

    $n = count($arr2);

  

    if(isSubset($arr1, $arr2, $m, $n))

        echo "arr2[] is subset of arr1[] ";

    else

        echo "arr2[] is not a subset of arr1[]";     

  
// Этот код предоставлен anuj_67.
?>


Выход:

arr2[] is subset of arr1[] 

Сложность времени: O (m * n)

Метод 2 (использовать сортировку и бинарный поиск ) :

  • Сортировка arr1 [], которая принимает O (mLogm)
  • Для каждого элемента arr2 [] выполните бинарный поиск в отсортированном arr1 [].
  • Если элемент не найден, вернуть 0.
  • Если присутствуют все элементы, вернуть 1.

C ++

// C ++ программа, чтобы найти ли массив
// это подмножество другого массива
#include<bits/stdc++.h>

using namespace std;

  
/ * Функциональные прототипы * /

void quickSort(int *arr, int si, int ei);

int binarySearch(int arr[], int low, 

                    int high, int x);

  
/ * Возвращает 1, если arr2 [] является подмножеством arr1 [] * /

bool isSubset(int arr1[], int arr2[],

                        int m, int n)

{

    int i = 0;

  

    quickSort(arr1, 0, m-1);

    for (i=0; i<n; i++)

    {

        if (binarySearch(arr1, 0, m - 1,

                        arr2[i]) == -1)

        return 0;

    }

      

    / * Если мы достигнем здесь, то все элементы

     arr2 [] присутствуют в arr1 [] * /

    return 1;

}

  
/ * СЛЕДУЮЩИЕ ФУНКЦИИ ТОЛЬКО ДЛЯ

    ПОИСК И СОРТИРОВКА ЦЕЛЬ * /

/ * Стандартная функция двоичного поиска * /

int binarySearch(int arr[], int low,

                    int high, int x)

{

    if(high >= low)

    {

        int mid = (low + high)/2; / * низкий + (высокий - низкий) / 2; * /

  

        / * Проверить, является ли arr [mid] первым появлением x.

        arr [mid] является первым появлением, если x является одним из следующих

        правда:

        (i) mid == 0 и arr [mid] == x

        (ii) arr [mid-1] <x и arr [mid] == x * /

        if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))

            return mid;

        else if(x > arr[mid])

            return binarySearch(arr, (mid + 1), high, x);

        else

            return binarySearch(arr, low, (mid -1), x);

    }

    return -1;

  

void exchange(int *a, int *b)

{

    int temp;

    temp = *a;

    *a = *b;

    *b = temp;

}

  

int partition(int A[], int si, int ei)

{

    int x = A[ei];

    int i = (si - 1);

    int j;

  

    for (j = si; j <= ei - 1; j++)

    {

        if(A[j] <= x)

        {

            i++;

            exchange(&A[i], &A[j]);

        }

    }

    exchange (&A[i + 1], &A[ei]);

    return (i + 1);

}

  
/ * Реализация быстрой сортировки
A [] -> Массив для сортировки
si -> Начальный индекс
ei -> Конечный индекс
* /

void quickSort(int A[], int si, int ei)

{

    int pi; / * Индекс разделения * /

    if(si < ei)

    {

        pi = partition(A, si, ei);

        quickSort(A, si, pi - 1);

        quickSort(A, pi + 1, ei);

    }

}

  
/ * Код водителя * /

int main()

{

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

    int arr2[] = {11, 3, 7, 1};

  

    int m = sizeof(arr1) / sizeof(arr1[0]);

    int n = sizeof(arr2) / sizeof(arr2[0]);

  

    if(isSubset(arr1, arr2, m, n))

        cout << "arr2[] is subset of arr1[] ";

    else

        cout << "arr2[] is not a subset of arr1[] "

  

    return 0;

}

  
// Этот код предоставлен Shivi_Aggarwal

С

// Программа на C, чтобы найти ли массив
// это подмножество другого массива
#include<stdio.h>
#include <stdbool.h>
/ * Функциональные прототипы * /

void quickSort(int *arr, int si, int ei);

int binarySearch(int arr[], int low, int high, int x);

  
/ * Возвращает 1, если arr2 [] является подмножеством arr1 [] * /

bool isSubset(int arr1[], int arr2[], int m, int n)

{

    int i = 0;

    

    quickSort(arr1, 0, m-1);

    for (i=0; i<n; i++)

    {

        if (binarySearch(arr1, 0, m-1, arr2[i]) == -1)

           return 0;

    }

      

    / * Если мы достигнем здесь, то все элементы arr2 []

      присутствуют в arr1 [] * /

    return 1;

}

   
/ * СЛЕДУЮЩИЕ ФУНКЦИИ ТОЛЬКО ДЛЯ ПОИСКА И ЦЕЛИ СОРТИРОВКИ * /
/ * Стандартная функция двоичного поиска * /

int binarySearch(int arr[], int low, int high, int x)

{

  if(high >= low)

  {

    int mid = (low + high)/2;  / * низкий + (высокий - низкий) / 2; * /

   

    / * Проверить, является ли arr [mid] первым появлением x.

        arr [mid] является первым появлением, если x является одним из следующих

        правда:

        (i) mid == 0 и arr [mid] == x

        (ii) arr [mid-1] <x и arr [mid] == x

     * /

    if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))

      return mid;

    else if(x > arr[mid])

      return binarySearch(arr, (mid + 1), high, x);

    else

      return binarySearch(arr, low, (mid -1), x);

  }

 return -1;

}  

  

void exchange(int *a, int *b)

{

    int temp;

    temp = *a;

    *a   = *b;

    *b   = temp;

}

   

int partition(int A[], int si, int ei)

{

    int x = A[ei];

    int i = (si - 1);

    int j;

   

    for (j = si; j <= ei - 1; j++)

    {

        if(A[j] <= x)

        {

            i++;

            exchange(&A[i], &A[j]);

        }

    }

    exchange (&A[i + 1], &A[ei]);

    return (i + 1);

}

   
/ * Реализация быстрой сортировки
A [] -> Массив для сортировки
si -> Начальный индекс
ei -> Конечный индекс
* /

void quickSort(int A[], int si, int ei)

{

    int pi;    / * Индекс разделения * /

    if(si < ei)

    {

        pi = partition(A, si, ei);

        quickSort(A, si, pi - 1);

        quickSort(A, pi + 1, ei);

    }

}

   
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

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

    int arr2[] = {11, 3, 7, 1};

    

    int m = sizeof(arr1)/sizeof(arr1[0]);

    int n = sizeof(arr2)/sizeof(arr2[0]);

  

    if(isSubset(arr1, arr2, m, n))

      printf("arr2[] is subset of arr1[] ");

    else

      printf("arr2[] is not a subset of arr1[] ");      

  

    return 0;

}

Джава

// Java-программа для определения наличия массива
// это подмножество другого массива

class Main

{

    / * Вернуть true, если arr2 [] является подмножеством arr1 [] * /

    static boolean isSubset(int arr1[], int arr2[], int m, int n)

    {

        int i = 0;

         

        sort(arr1, 0, m-1);

        for (i=0; i<n; i++)

        {

            if (binarySearch(arr1, 0, m-1, arr2[i]) == -1)

               return false;

        }

           

        / * Если мы достигнем здесь, то все элементы arr2 []

          присутствуют в arr1 [] * /

        return true;

    }

        

    / * СЛЕДУЮЩИЕ ФУНКЦИИ ТОЛЬКО ДЛЯ ПОИСКА И ЦЕЛИ СОРТИРОВКИ * /

    / * Стандартная функция двоичного поиска * /

    static int binarySearch(int arr[], int low, int high, int x)

    {

      if(high >= low)

      {

        int mid = (low + high)/2/ * низкий + (высокий - низкий) / 2; * /

        

        / * Проверить, является ли arr [mid] первым появлением x.

            arr [mid] является первым появлением, если x является одним из следующих

            правда:

            (i) mid == 0 и arr [mid] == x

            (ii) arr [mid-1] <x и arr [mid] == x

         * /

        if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))

          return mid;

        else if(x > arr[mid])

          return binarySearch(arr, (mid + 1), high, x);

        else

          return binarySearch(arr, low, (mid -1), x);

      }

     return -1;

    }  

       

    / * Эта функция принимает последний элемент в качестве оси,

       помещает элемент поворота в правильное положение

       положение в отсортированном массиве, и помещает все

       меньше (меньше, чем шарнир) слева от

       стержень и все большие элементы направо

       оси * /

    static int partition(int arr[], int low, int high)

    {

        int pivot = arr[high]; 

        int i = (low-1); // индекс меньшего элемента

        for (int j=low; j<high; j++)

        {

            // Если текущий элемент меньше или

            // равно pivot

            if (arr[j] <= pivot)

            {

                i++;

   

                // поменять местами arr [i] и arr [j]

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

   

        // поменять местами arr [i + 1] и arr [high] (или pivot)

        int temp = arr[i+1];

        arr[i+1] = arr[high];

        arr[high] = temp;

   

        return i+1;

    }

   

   

    / * Основная функция, которая реализует QuickSort ()

      arr [] -> Массив для сортировки,

      низкий -> Начальный индекс,

      высокий -> конечный индекс * /

    static void sort(int arr[], int low, int high)

    {

        if (low < high)

        {

            / * pi - индекс разбиения, arr [pi] -

              сейчас в нужном месте * /

            int pi = partition(arr, low, high);

   

            // Рекурсивно сортировать элементы перед

            // раздел и после раздела

            sort(arr, low, pi-1);

            sort(arr, pi+1, high);

        }

    }

       

    public static void main(String args[])

    {

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

        int arr2[] = {11, 3, 7, 1};

         

        int m = arr1.length;

        int n = arr2.length;

       

        if(isSubset(arr1, arr2, m, n))

          System.out.print("arr2[] is subset of arr1[] ");

        else

          System.out.print("arr2[] is not a subset of arr1[]");  

    }

}

python3

# Python3 программа для определения наличия массива
# является подмножеством другого массива

  
# Возвращает 1, если arr2 [] является подмножеством arr1 []

def isSubset(arr1, arr2, m, n):

    i = 0;

  

    quickSort(arr1, 0, m-1);

    for i in range(n):

        if (binarySearch(arr1, 0, m - 1,arr2[i]) == -1):

            return 0;

      

    # Если мы достигнем здесь, то все элементы

    № arr2 [] присутствует в arr1 []

    return 1;

  
# СЛЕДУЮЩИЕ ФУНКЦИИ ТОЛЬКО ДЛЯ
# ПОИСК И СОРТИРОВКА ЦЕЛЬ
# Стандартная функция двоичного поиска

def binarySearch(arr, low, high, x):

    if(high >= low):

        mid = (low + high)//2;

  

        # Проверьте, является ли arr [mid] первым появлением x.

        # arr [mid] является первым появлением, если x является одним из следующих

        # правда:

        # (i) mid == 0 и arr [mid] == x

        # (ii) arr [mid-1] <x и arr [mid] == x

        if(( mid == 0 or x > arr[mid-1]) and (arr[mid] == x)):

            return mid;

        elif(x > arr[mid]):

            return binarySearch(arr, (mid + 1), high, x);

        else:

            return binarySearch(arr, low, (mid -1), x);

  

    return -1;

  

  

def partition(A, si, ei):

    x = A[ei];

    i = (si - 1);

  

    for j in range(si,ei):

        if(A[j] <= x):

            i+=1;

            A[i],A[j] = A[j],A[i];

    A[i + 1],A[ei] = A[ei],A[i+1];

    return (i + 1);

  
# Реализация быстрой сортировки
# A [] -> Массив для сортировки
# si -> Начальный индекс
# ei -> Конечный индекс

  

def quickSort(A, si, ei):

    # Индекс разделения

    if(si < ei):

        pi = partition(A, si, ei);

        quickSort(A, si, pi - 1);

        quickSort(A, pi + 1, ei);

  
# Код драйвера

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

arr2 = [11, 3, 7, 1];

  

m = len(arr1);

n = len(arr2);

  

if(isSubset(arr1, arr2, m, n)):

    print("arr2[] is subset of arr1[] ");

else:

    print("arr2[] is not a subset of arr1[] "); 

  

  
# Этот код предоставлен chandan_jnu

C #

// C # программа, чтобы найти ли массив
// это подмножество другого массива

using System;

                  

      

public class GFG

{

    / * Вернуть true, если arr2 [] является подмножеством arr1 [] * /

    static bool isSubset(int []arr1, int []arr2, int m, int n)

    {

        int i = 0;

          

        sort(arr1, 0, m-1);

        for (i=0; i<n; i++)

        {

            if (binarySearch(arr1, 0, m-1, arr2[i]) == -1)

               return false;

        }

            

        / * Если мы достигнем здесь, то все элементы arr2 []

          присутствуют в arr1 [] * /

        return true;

    }

         

    / * СЛЕДУЮЩИЕ ФУНКЦИИ ТОЛЬКО ДЛЯ ПОИСКА И ЦЕЛИ СОРТИРОВКИ * /

    / * Стандартная функция двоичного поиска * /

    static int binarySearch(int []arr, int low, int high, int x)

    {

      if(high >= low)

      {

        int mid = (low + high)/2;  / * низкий + (высокий - низкий) / 2; * /

         

        / * Проверить, является ли arr [mid] первым появлением x.

            arr [mid] является первым появлением, если x является одним из следующих

            правда:

            (i) mid == 0 и arr [mid] == x

            (ii) arr [mid-1] <x и arr [mid] == x

         * /

        if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))

          return mid;

        else if(x > arr[mid])

          return binarySearch(arr, (mid + 1), high, x);

        else

          return binarySearch(arr, low, (mid -1), x);

      }

     return -1;

    }  

        

    / * Эта функция принимает последний элемент в качестве оси,

       помещает элемент поворота в правильное положение

       положение в отсортированном массиве, и помещает все

       меньше (меньше, чем шарнир) слева от

       стержень и все большие элементы направо

       оси * /

    static int partition(int []arr, int low, int high)

    {

        int pivot = arr[high]; 

        int i = (low-1); // индекс меньшего элемента

        int temp=0;

        for (int j=low; j<high; j++)

        {

            // Если текущий элемент меньше или

            // равно pivot

            if (arr[j] <= pivot)

            {

                i++;

    

                // поменять местами arr [i] и arr [j]

                temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

    

        // поменять местами arr [i + 1] и arr [high] (или pivot)

        temp = arr[i+1];

        arr[i+1] = arr[high];

        arr[high] = temp;

    

        return i+1;

    }

    

    

    / * Основная функция, которая реализует QuickSort ()

      arr [] -> Массив для сортировки,

      низкий -> Начальный индекс,

      высокий -> конечный индекс * /

    static void sort(int []arr, int low, int high)

    {

        if (low < high)

        {

            / * pi - индекс разбиения, arr [pi] -

              сейчас в нужном месте * /

            int pi = partition(arr, low, high);

    

            // Рекурсивно сортировать элементы перед

            // раздел и после раздела

            sort(arr, low, pi-1);

            sort(arr, pi+1, high);

        }

    }

        

    public static void Main()

    {

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

        int []arr2= {11, 3, 7, 1};

          

        int m = arr1.Length;

        int n = arr2.Length;

        

        if(isSubset(arr1, arr2, m, n))

          Console.Write("arr2[] is subset of arr1[] ");

        else

          Console.Write("arr2[] is not a subset of arr1[]");  

    }

}
// Этот код предоставлен 29AjayKumar

PHP

<?php
// PHP-программа для определения наличия массива
// это подмножество другого массива

  
/ * Возвращает 1, если arr2 [] является подмножеством arr1 [] * /

function isSubset($arr1, $arr2,

                        $m, $n)

{

    $i = 0;

  

    quickSort($arr1, 0, $m-1);

    for ($i = 0; $i < $n; $i++)

    {

        if (binarySearch($arr1, 0, $m - 1,

                        $arr2[$i]) == -1)

        return 0;

    }

      

    / * Если мы достигнем здесь, то все элементы

    arr2 [] присутствуют в arr1 [] * /

    return 1;

}

  
/ * СЛЕДУЮЩИЕ ФУНКЦИИ ТОЛЬКО ДЛЯ

    ПОИСК И СОРТИРОВКА ЦЕЛЬ * /

/ * Стандартная функция двоичного поиска * /

function binarySearch($arr, $low, $high, $x)

{

    if($high >= $low)

    {

        $mid = (int)(($low + $high)/2); / * низкий + (высокий - низкий) / 2; * /

  

        / * Проверить, является ли arr [mid] первым появлением x.

        arr [mid] является первым появлением, если x является одним из следующих

        правда:

        (i) mid == 0 и arr [mid] == x

        (ii) arr [mid-1] <x и arr [mid] == x * /

        if(( $mid == 0 || $x > $arr[$mid-1]) && ($arr[$mid] == $x))

            return $mid;

        else if($x > $arr[$mid])

            return binarySearch($arr, ($mid + 1), $high, $x);

        else

            return binarySearch($arr, $low, ($mid -1), $x);

    }

    return -1;

  

function exchange(&$a, &$b)

{

  

    $temp = $a;

    $a = $b;

    $b = $temp;

}

  

function partition(&$A, $si, $ei)

{

    $x = $A[$ei];

    $i = ($si - 1);

  

    for ($j = $si; $j <= $ei - 1; $j++)

    {

        if($A[$j] <= $x)

        {

            $i++;

            exchange($A[$i], $A[$j]);

        }

    }

    exchange ($A[$i + 1], $A[$ei]);

    return ($i + 1);

}

  
/ * Реализация быстрой сортировки
A [] -> Массив для сортировки
si -> Начальный индекс
ei -> Конечный индекс
* /

function quickSort(&$A, $si, $ei)

{

    / * Индекс разделения * /

    if($si < $ei)

    {

        $pi = partition($A, $si, $ei);

        quickSort($A, $si, $pi - 1);

        quickSort($A, $pi + 1, $ei);

    }

}

  

    / * Код водителя * /

    $arr1 = array(11, 1, 13, 21, 3, 7);

    $arr2 = array(11, 3, 7, 1);

  

    $m = count($arr1);

    $n = count($arr2);

  

    if(isSubset($arr1, $arr2, $m, $n))

        echo "arr2[] is subset of arr1[] ";

    else

        echo "arr2[] is not a subset of arr1[] "

  

  
// Этот код предоставлен chandan_jnu
?>


Выход:

arr2 is a subset of arr1

Сложность времени: O (mLogm + nLogm). Обратите внимание, что это будет сложнее, если для сортировки используется алгоритм mLogm, чего нет в приведенном выше коде. В приведенном выше коде используется быстрая сортировка, а сложность быстрой сортировки в наихудшем случае равна O (m ^ 2)

Способ 3 (использовать сортировку и объединение )

  • Сортируйте оба массива: arr1 [] и arr2 [], который принимает O (mLogm + nLogn)
  • Используйте процесс слияния типа, чтобы увидеть, присутствуют ли все элементы отсортированного arr2 [] в отсортированном arr1 [].

Спасибо Парфсарти за предложение этого метода.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа, чтобы найти ли массив
// это подмножество другого массива
#include <bits/stdc++.h>

using namespace std;

  

/ * Возвращает 1, если arr2 [] является подмножеством arr1 [] * / 

bool isSubset(int arr1[], int arr2[], int m, int n)

{

    int i = 0, j = 0;

      

    if (m < n)

       return 0;

      

    // Сортировка обоих массивов

    sort(arr1, arr1 + m);

    sort(arr2, arr2 + n); 

      

    // Итерация, пока они не превысят свои размеры

    while (i < n && j < m )

    

        // Если элемент меньше чем

        // Переместить aheaad в первый массив

        if( arr1[j] <arr2[i] )

            j++;

        // Если оба равны, то сдвигаем их обоих вперед

        else if( arr1[j] == arr2[i] )

        {

            j++;

            i++;

        }

  

        // Если у нас нет элемента меньше

        // или равен второму массиву, затем ломаемся

        else if( arr1[j] > arr2[i] )

            return 0;

    }

   

    return  (i < n)? false : true;

  
// Код драйвера

int main()

{

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

    int arr2[] = {11, 3, 7, 1};

    

    int m = sizeof(arr1)/sizeof(arr1[0]);

    int n = sizeof(arr2)/sizeof(arr2[0]);

  

    if(isSubset(arr1, arr2, m, n))

      printf("arr2[] is subset of arr1[] ");

    else

      printf("arr2[] is not a subset of arr1[] ");      

  

    return 0;

}

Джава

// Java-код для определения, является ли массив подмножеством
// другой массив

import java.util.Arrays;

class GFG

{

    / * Вернуть true, если arr2 [] является подмножеством arr1 [] * /

    static boolean isSubset(int arr1[], int arr2[], int m,

                                                   int n)

    {

        int i = 0, j = 0;

              

        if(m < n)

        return false;

          

        Arrays.sort(arr1); // сортирует arr1

        Arrays.sort(arr2); // сортирует arr2

  

        while( i < n && j < m )

        {

            if( arr1[j] < arr2[i] )

                j++;

            else if( arr1[j] == arr2[i] )

            {

                j++;

                i++;

            }

            else if( arr1[j] > arr2[i] )

                return false;

        }

          

        if( i < n )

            return false;

        else

            return true;

    

          

    public static void main(String[] args) 

    

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

        int arr2[] = {11, 3, 7, 1};

          

        int m = arr1.length;

        int n = arr2.length;

          

        if(isSubset(arr1, arr2, m, n))

        System.out.println("arr2 is a subset of arr1");

        else

        System.out.println("arr2 is not a subset of arr1");

    }

}
// Этот код предоставлен Камалем Равалом

python3

# Python3 программа для определения наличия массива
# является подмножеством другого массива

  
# Возвращает 1, если arr2 [] является подмножеством arr1 [] * /

def isSubset(arr1, arr2, m, n):

    i = 0

    j = 0

    if m < n:

        return 0

          

    arr1.sort()

    arr2.sort()

  

    while i < n and j < m:

        if arr1[j] < arr2[i]:

            j += 1

        elif arr1[j] == arr2[i]:

            j += 1

            i += 1

        elif arr1[j] > arr2[i]:

            return 0

    return False if i < n else True

  
# Код драйвера

arr1 = [11, 1, 13, 21, 3, 7]

arr2 = [11, 3, 7, 1]

  

m = len(arr1)

n = len(arr2)

if isSubset(arr1, arr2, m, n) == True:

    print("arr2 is subset of arr1 ")

else:

    printf("arr2 is not a subset of arr1 ")

  
# Этот код предоставлен Shrikant13

C #

// C # код, чтобы найти ли массив
// это подмножество другого массива

using System;

class GFG {

      

    // Возвращаем true, если arr2 []

    // подмножество arr1 [] * /

    static bool isSubset(int []arr1, 

                         int []arr2, 

                         int m,

                         int n)

    {

        int i = 0, j = 0;

              

        if(m < n)

            return false;

          

        // сортирует arr1

        Array.Sort(arr1); 

          

        // сортирует arr2

        Array.Sort(arr2); 

  

        while( i < n && j < m )

        {

            if( arr1[j] < arr2[i] )

                j++;

            else if( arr1[j] == arr2[i] )

            {

                j++;

                i++;

            }

            else if( arr1[j] > arr2[i] )

                return false;

        }

          

        if( i < n )

            return false;

        else

            return true;

    

          

    // Код драйвера

    public static void Main() 

    

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

        int []arr2 = {11, 3, 7, 1};

          

        int m = arr1.Length;

        int n = arr2.Length;

          

        if(isSubset(arr1, arr2, m, n))

            Console.Write("arr2 is a subset of arr1");

        else

            Console.Write("arr2 is not a subset of arr1");

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP-программа для определения наличия массива
// это подмножество другого массива

  
/ * Возвращает 1, если arr2 [] является подмножеством arr1 [] * /

function isSubset( $arr1, $arr2, $m, $n)

{

    $i = 0; $j = 0;

      

    if ($m < $n)

        return 0;

  

    sort($arr1);

    sort($arr2);

      

    while ($i < $n and $j < $m )

    {

        if( $arr1[$j] <$arr2[$i] )

            $j++;

        else if( $arr1[$j] == $arr2[$i] )

        {

            $j++;

            $i++;

        }

        else if( $arr1[$j] > $arr2[$i] )

            return 0;

    }

  

    return ($i < $n) ? false : true;

  
/ * Программа драйвера для проверки вышеуказанных функций * /

  

    $arr1 = array(11, 1, 13, 21, 3, 7);

    $arr2 = array(11, 3, 7, 1);

  

    $m = count($arr1);

    $n = count($arr2);

  

    if(isSubset($arr1, $arr2, $m, $n))

        echo "arr2[] is subset of arr1[] ";

    else

        echo "arr2[] is not a subset of arr1[] "

  
// Этот код предоставлен anuj_67.
?>


Выход:

arr2 is a subset of arr1

Сложность времени: O (mLogm + nLogn), что лучше, чем метод 2. Обратите внимание, что это будет сложность, если алгоритм nLogn используется для сортировки обоих массивов, что не имеет место в приведенном выше коде. В приведенном выше коде используется быстрая сортировка, а сложность быстрой сортировки в наихудшем случае равна O (n ^ 2)

Метод 4 (использовать хеширование)

  • Создайте хеш-таблицу для всех элементов arr1 [].
  • Пройдите через arr2 [] и найдите каждый элемент arr2 [] в хэш-таблице. Если элемент не найден, вернуть 0.
  • Если все элементы найдены, вернуть 1.

Ниже приведена реализация вышеуказанного подхода:

Джава

// Java-код для определения, является ли массив подмножеством
// другой массив

import java.util.HashSet;

class GFG

{

    / * Вернуть true, если arr2 [] является подмножеством arr1 [] * /

    static boolean isSubset(int arr1[], int arr2[], int m,

                                                 int n)

    {

        HashSet<Integer> hset= new HashSet<>();

          

        // hset хранит все значения arr1

        for(int i = 0; i < m; i++)

        {

            if(!hset.contains(arr1[i]))

                hset.add(arr1[i]);

        }

              

        // цикл, чтобы проверить, все ли элементы arr2 также

        // лежит в arr1

        for(int i = 0; i < n; i++)

        {

            if(!hset.contains(arr2[i]))

                return false;

        }

        return true;

    

  

    public static void main(String[] args) 

    

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

        int arr2[] = {11, 3, 7, 1};

          

        int m = arr1.length;

        int n = arr2.length;

              

        if(isSubset(arr1, arr2, m, n))

        System.out.println("arr2 is a subset of arr1");

        else

        System.out.println("arr2 is not a subset of arr1");

    }

}
// Этот код предоставлен Камалем Равалом

C #

// код C #, чтобы определить, является ли массив
// подмножество другого массива

using System;

using System.Collections.Generic;

  

class GFG

{
/ * Вернуть true, если arr2 [] является

   подмножество arr1 [] * /

public static bool isSubset(int[] arr1, 

                            int[] arr2,

                            int m, int n)

{

    HashSet<int> hset = new HashSet<int>();

  

    // hset хранит все значения arr1

    for (int i = 0; i < m; i++)

    {

        if (!hset.Contains(arr1[i]))

        {

            hset.Add(arr1[i]);

        }

    }

  

    // цикл, чтобы проверить, все ли элементы

    // из arr2 также лежит в arr1

    for (int i = 0; i < n; i++)

    {

        if (!hset.Contains(arr2[i]))

        {

            return false;

        }

    }

    return true;

}

  
// Код драйвера

public static void Main(string[] args)

{

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

    int[] arr2 = new int[] {11, 3, 7, 1};

  

    int m = arr1.Length;

    int n = arr2.Length;

  

    if (isSubset(arr1, arr2, m, n))

    {

        Console.WriteLine("arr2 is a subset of arr1");

    }

    else

    {

        Console.WriteLine("arr2 is not a subset of arr1");

    }

}
}

  
// Этот код предоставлен Shrikant13


Выход:

arr2 is a subset of arr1

Обратите внимание, что метод 1, метод 2 и метод 4 не обрабатывают случаи, когда у нас есть дубликаты в arr2 []. Например, {1, 4, 4, 2} не является подмножеством {1, 4, 2}, но эти методы будут печатать его как подмножество.

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Найти, является ли массив подмножеством другого массива | Добавлен метод 3

0.00 (0%) 0 votes