Рубрики

Найти объединение и пересечение двух несортированных массивов

Учитывая два несортированных массива, которые представляют два набора (элементы в каждом массиве различны), найдите объединение и пересечение двух массивов.

Например, если входные массивы:
arr1 [] = {7, 1, 5, 2, 3, 6}
arr2 [] = {3, 8, 6, 20, 7}
Тогда ваша программа должна напечатать Union как {1, 2, 3, 5, 6, 7, 8, 20} и Intersection как {3, 6}. Обратите внимание, что элементы объединения и пересечения могут быть напечатаны в любом порядке.

Метод 1 (Наивный)
Союз:
1) Инициализировать объединение U как пустое.
2) Скопировать все элементы первого массива в U.
3) Выполните следующие действия для каждого элемента x второго массива:
… ..A) Если x отсутствует в первом массиве, скопируйте x в U.
4) Вернуть У.

пересечения:
1) Инициализировать пересечение I как пустое.
2) Выполните следующие действия для каждого элемента x первого массива.
… ..A) Если x присутствует во втором массиве, скопируйте x в I.
4) Вернуть И.

Временная сложность этого метода составляет O (mn) для обеих операций. Здесь m и n — количество элементов в arr1 [] и arr2 [] соответственно.

Способ 2 (использовать сортировку)
1) Сортировка arr1 [] и arr2 []. Этот шаг занимает O (mLogm + nLogn) время.
2) Используйте O (m + n) алгоритмы, чтобы найти объединение и пересечение двух отсортированных массивов .

Общая временная сложность этого метода составляет O (mLogm + nLogn).

Способ 3 (использовать сортировку и поиск)
Союз:
1) Инициализировать объединение U как пустое.
2) Найдите меньшее из m и n и отсортируйте меньший массив.
3) Скопируйте меньший массив в U.
4) Для каждого элемента х большего массива выполните следующее
…… .b) Бинарный поиск х в меньшем массиве. Если x отсутствует, скопируйте его в U.
5) Вернуть У.

пересечения:
1) Инициализировать пересечение I как пустое.
2) Найдите меньшее из m и n и отсортируйте меньший массив.
3) Для каждого элемента х большего массива выполните следующее
…… .b) Бинарный поиск х в меньшем массиве. Если x присутствует, скопируйте его в I.
4) Вернуть И.

Временная сложность этого метода составляет минимум (mLogm + nLogm, mLogn + nLogn), который также можно записать как O ((m + n) Logm, (m + n) Logn). Этот подход работает намного лучше, чем предыдущий, когда разница между размерами двух массивов значительна.

Спасибо use_the_force за предложение этого метода в комментарии здесь .

Ниже приведена реализация этого метода.

C ++

// Программа на C ++ для печати объединения и пересечения
/// из двух несортированных массивов
#include <iostream>
#include <algorithm>

using namespace std;

  

int binarySearch(int arr[], int l, int r, int x);

  
// Печатает объединение arr1 [0..m-1] и arr2 [0..n-1]

void printUnion(int arr1[], int arr2[], int m, int n)

{

    // Прежде чем найти объединение, убедитесь, что arr1 [0..m-1]

    // меньше

    if (m > n)

    {

        int *tempp = arr1;

        arr1 = arr2;

        arr2 = tempp;

  

        int temp = m;

        m = n;

        n = temp;

    }

  

    // Теперь arr1 [] меньше

  

    // сортируем первый массив и печатаем его элементы (эти два

    // шаги можно поменять местами, так как порядок вывода не важен)

    sort(arr1, arr1 + m);

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

        cout << arr1[i] << " ";

  

    // Поиск каждого элемента большего массива в меньшем массиве

    // и распечатать элемент, если не найден

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

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

            cout << arr2[i] << " ";

}

  
// Печатает пересечение arr1 [0..m-1] и arr2 [0..n-1]

void printIntersection(int arr1[], int arr2[], int m, int n)

{

    // Прежде чем найти пересечение, убедитесь, что arr1 [0..m-1]

    // меньше

    if (m > n)

    {

        int *tempp = arr1;

        arr1 = arr2;

        arr2 = tempp;

  

        int temp = m;

        m = n;

        n = temp;

    }

  

    // Теперь arr1 [] меньше

  

    // Сортировать меньший массив arr1 [0..m-1]

    sort(arr1, arr1 + m);

  

    // Поиск каждого элемента большего массива в меньшем

    // массив и печать элемента, если найден

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

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

            cout << arr2[i] << " ";

}

  
// Рекурсивная функция двоичного поиска. Возвращается
// расположение x в заданном массиве arr [l..r] присутствует,
// иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

    if (r >= l)

    {

        int mid = l + (r - l)/2;

  

        // Если элемент присутствует в самой середине

        if (arr[mid] == x)  return mid;

  

        // Если элемент меньше среднего, то он может только

        // быть представленным в левом подмассиве

        if (arr[mid] > x) 

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

  

        // Иначе элемент может присутствовать только в правом подмассиве

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

    }

  

    // Мы достигаем здесь, когда элемент отсутствует в массиве

    return -1;

}

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

int main()

{

    int arr1[] = {7, 1, 5, 2, 3, 6};

    int arr2[] = {3, 8, 6, 20, 7};

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

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

    cout << "Union of two arrays is n";

    printUnion(arr1, arr2, m, n);

    cout << "nIntersection of two arrays is n";

    printIntersection(arr1, arr2, m, n);

    return 0;

}

Джава

// Java-программа для печати объединения и пересечения
/// из двух несортированных массивов

import java.util.Arrays;

  

class UnionAndIntersection 

{

    // Печатает объединение arr1 [0..m-1] и arr2 [0..n-1]

    void printUnion(int arr1[], int arr2[], int m, int n) 

    {

        // Прежде чем найти объединение, убедитесь, что arr1 [0..m-1]

        // меньше

        if (m > n) 

        {

            int tempp[] = arr1;

            arr1 = arr2;

            arr2 = tempp;

  

            int temp = m;

            m = n;

            n = temp;

        }

  

        // Теперь arr1 [] меньше

        // сортируем первый массив и печатаем его элементы (эти два

        // шаги можно поменять местами, так как порядок вывода не важен)

        Arrays.sort(arr1);

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

            System.out.print(arr1[i] + " ");

  

        // Поиск каждого элемента большего массива в меньшем массиве

        // и распечатать элемент, если не найден

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

        {

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

                System.out.print(arr2[i] + " ");

        }

    }

  

    // Печатает пересечение arr1 [0..m-1] и arr2 [0..n-1]

    void printIntersection(int arr1[], int arr2[], int m, int n) 

    {

        // Прежде чем найти пересечение, убедитесь, что arr1 [0..m-1]

        // меньше

        if (m > n) 

        {

            int tempp[] = arr1;

            arr1 = arr2;

            arr2 = tempp;

  

            int temp = m;

            m = n;

            n = temp;

        }

  

        // Теперь arr1 [] меньше

        // Сортировать меньший массив arr1 [0..m-1]

        Arrays.sort(arr1);

  

        // Поиск каждого элемента большего массива в меньшем массиве

        // и распечатать элемент, если найден

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

        {

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

                System.out.print(arr2[i] + " ");

        }

    }

  

    // Рекурсивная функция двоичного поиска. Возвращает местоположение х в

    // данный массив arr [l..r] присутствует, иначе -1

    int binarySearch(int arr[], int l, int r, int x) 

    {

        if (r >= l) 

        {

            int mid = l + (r - l) / 2;

  

            // Если элемент присутствует в самой середине

            if (arr[mid] == x)

                return mid;

  

            // Если элемент меньше среднего, то он может только

            // присутствовать в левом подмассиве

            if (arr[mid] > x)

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

  

            // Иначе элемент может присутствовать только в правом подмассиве

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

        }

  

        // Мы достигаем здесь, когда элемент отсутствует в массиве

        return -1;

    }

  

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

    public static void main(String[] args) 

    {

        UnionAndIntersection u_i = new UnionAndIntersection();

        int arr1[] = {7, 1, 5, 2, 3, 6};

        int arr2[] = {3, 8, 6, 20, 7};

        int m = arr1.length;

        int n = arr2.length;

        System.out.println("Union of two arrays is ");

        u_i.printUnion(arr1, arr2, m, n);

        System.out.println("");

        System.out.println("Intersection of two arrays is ");

        u_i.printIntersection(arr1, arr2, m, n);

    }

}

python3

# Программа Python3 для печати объединения и пересечения
# из двух несортированных массивов

  
# Выводит объединение arr1 [0..m-1] и arr2 [0..n-1]

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

  

    # Прежде чем найти объединение, убедитесь, что arr1 [0..m-1]

    # меньше

    if (m > n):

        tempp = arr1;

        arr1 = arr2;

        arr2 = tempp;

  

        temp = m;

        m = n;

        n = temp;

  

    # Теперь arr1 [] меньше

  

    # Сортировать первый массив и распечатать его элементы (эти два

    # шаги можно поменять местами, так как порядок вывода не важен)

    arr1.sort();

    for i in range(0,m):

        print(arr1[i],end=" ");

  

    # Поиск каждого элемента большего массива в меньшем массиве

    # и распечатать элемент, если не найден

    for i in range(0,n):

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

            print(arr2[i],end=" ");

  
# Печатает пересечение arr1 [0..m-1] и arr2 [0..n-1]

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

  

    # Прежде чем найти пересечение, убедитесь, что arr1 [0..m-1]

    # меньше

    if (m > n):

        tempp = arr1;

        arr1 = arr2;

        arr2 = tempp;

  

        temp = m;

        m = n;

        n = temp;

  

    # Теперь arr1 [] меньше

  

    # Сортировать меньший массив arr1 [0..m-1]

    arr1.sort();

  

    # Поиск каждого элемента большего массива в меньшем

    # массив и распечатать элемент, если найден

    for i in range(0,n):

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

            print(arr2[i],end=" ");

  
# Рекурсивная функция двоичного поиска. Возвращается
# местоположение x в данном массиве присутствует arr [l..r],
# иначе -1

def binarySearch(arr, l, r,x):

  

    if (r >= l):

        mid = int(l + (r - l)/2);

  

        # Если элемент присутствует в самой середине

        if (arr[mid] == x):

            return mid;

  

        # Если элемент меньше середины, то он может только

        # быть представленным в левом подмассиве

        if (arr[mid] > x):

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

  

        # В противном случае элемент может присутствовать только в правом подмассиве

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

  

    # Мы достигаем здесь, когда элемент не присутствует в массиве

    return -1;

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

arr1 = [7, 1, 5, 2, 3, 6];

arr2 = [3, 8, 6, 20, 7];

m = len(arr1);

n = len(arr2);

print("Union of two arrays is ");

printUnion(arr1, arr2, m, n);

print("\nIntersection of two arrays is ");

printIntersection(arr1, arr2, m, n);

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

C #

// AC # программа для печати объединения и
// пересечение двух несортированных массивов

using System;

  

class GFG

{
// Печатает объединение arr1 [0..m-1] и arr2 [0..n-1]

static void printUnion(int []arr1, int []arr2,

                                   int m, int n) 

{

    // Прежде чем найти объединение, сделайте

    // уверен, что arr1 [0..m-1] меньше

    if (m > n) 

    {

        int []tempp = arr1;

        arr1 = arr2;

        arr2 = tempp;

  

        int temp = m;

        m = n;

        n = temp;

    }

  

    // Теперь arr1 [] меньше

    // Сортировка первого массива и печать

    // его элементы (эти два шага могут

    // меняем местами как порядок вывода

    // не важный)

    Array.Sort(arr1);

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

        Console.Write(arr1[i] + " ");

  

    // Поиск каждого элемента большего

    // массив в меньшем массиве и печать

    // элемент, если не найден

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

    {

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

                         arr2[i]) == -1)

            Console.Write(arr2[i] + " ");

    }

}

  
// Печатает пересечение arr1 [0..m-1]
// и arr2 [0..n-1]

static void printIntersection(int []arr1,

                              int []arr2, 

                              int m, int n) 

{

    // Прежде чем найти пересечение,

    // убедитесь, что arr1 [0..m-1] меньше

    if (m > n) 

    {

        int []tempp = arr1;

        arr1 = arr2;

        arr2 = tempp;

  

        int temp = m;

        m = n;

        n = temp;

    }

  

    // Теперь arr1 [] меньше

    // Сортировать меньший массив arr1 [0..m-1]

    Array.Sort(arr1);

  

    // Поиск каждого элемента большего массива в

    // уменьшаем массив и печатаем элемент, если найден

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

    {

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

            Console.Write(arr2[i] + " ");

    }

}

  
// Рекурсивная функция двоичного поиска.
// Возвращает местоположение х в заданном
// массив arr [l..r] присутствует, иначе -1

static int binarySearch(int []arr, int l, 

                        int r, int x) 

{

    if (r >= l) 

    {

        int mid = l + (r - l) / 2;

  

        // Если элемент присутствует в

        // сама середина

        if (arr[mid] == x)

            return mid;

  

        // Если элемент меньше середины, то он

        // может присутствовать только в левом подмассиве

        if (arr[mid] > x)

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

  

        // иначе элемент может быть только

        // присутствует в правом подмассиве

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

    }

  

    // Мы достигаем здесь, когда элемент

    // отсутствует в массиве

    return -1;

}

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

static public void Main ()

{

    int []arr1 = {7, 1, 5, 2, 3, 6};

    int []arr2 = {3, 8, 6, 20, 7};

    int m = arr1.Length;

    int n = arr2.Length;

    Console.WriteLine("Union of two arrays is ");

    printUnion(arr1, arr2, m, n);

    Console.WriteLine("");

    Console.WriteLine("Intersection of two arrays is ");

    printIntersection(arr1, arr2, m, n);

}
}

  
// Этот код добавлен
// по Sach_Code

PHP

<?php
// PHP-программа для печати объединения и пересечения
/// из двух несортированных массивов

  
// Печатает объединение arr1 [0..m-1] и arr2 [0..n-1]

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

{

    // Прежде чем найти объединение, убедитесь, что arr1 [0..m-1]

    // меньше

    if ($m > $n)

    {

        $tempp = $arr1;

        $arr1 = $arr2;

        $arr2 = $tempp;

  

        $temp = $m;

        $m = $n;

        $n = $temp;

    }

  

    // Теперь arr1 [] меньше

  

    // сортируем первый массив и печатаем его элементы (эти два

    // шаги можно поменять местами, так как порядок вывода не важен)

    sort($arr1);

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

        echo $arr1[$i]." ";

  

    // Поиск каждого элемента большего массива в меньшем массиве

    // и распечатать элемент, если не найден

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

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

            echo $arr2[$i]." ";

}

  
// Печатает пересечение arr1 [0..m-1] и arr2 [0..n-1]

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

{

    // Прежде чем найти пересечение, убедитесь, что arr1 [0..m-1]

    // меньше

    if ($m > $n)

    {

        $tempp = $arr1;

        $arr1 = $arr2;

        $arr2 = $tempp;

  

        $temp = $m;

        $m = $n;

        $n = $temp;

    }

  

    // Теперь arr1 [] меньше

  

    // Сортировать меньший массив arr1 [0..m-1]

    sort($arr1);

  

    // Поиск каждого элемента большего массива в меньшем

    // массив и печать элемента, если найден

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

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

            echo $arr2[$i]." ";

}

  
// Рекурсивная функция двоичного поиска. Возвращается
// расположение x в заданном массиве arr [l..r] присутствует,
// иначе -1

function binarySearch($arr, $l, $r,$x)

{

    if ($r >= $l)

    {

        $mid = (int)($l + ($r - $l)/2);

  

        // Если элемент присутствует в самой середине

        if ($arr[$mid] == $x) return $mid;

  

        // Если элемент меньше среднего, то он может только

        // быть представленным в левом подмассиве

        if ($arr[$mid] > $x

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

  

        // Иначе элемент может присутствовать только в правом подмассиве

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

    }

  

    // Мы достигаем здесь, когда элемент отсутствует в массиве

    return -1;

}

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

    $arr1 = array(7, 1, 5, 2, 3, 6);

    $arr2 = array(3, 8, 6, 20, 7);

    $m = count($arr1);

    $n = count($arr2);

    echo "Union of two arrays is \n";

    printUnion($arr1, $arr2, $m, $n);

    echo "\nIntersection of two arrays is \n";

    printIntersection($arr1, $arr2, $m, $n);

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


Выход:

Union of two arrays is
3 6 7 8 20 1 5 2
Intersection of two arrays is
7 3 6

Другой подход (когда элементы в массиве могут не различаться):

С

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

  

using namespace std;

  
// Функция для поиска пересечения

void intersection(int a[], int b[], int n, int m)

{

    int i = 0, j = 0;

      

    while (i < n && j < m) 

    {

                  

        if (a[i] > b[j]) 

        {

            j++;

        

                  

        else 

        if (b[j] > a[i]) 

        {

            i++;

        

        else 

        {

            // когда оба равны

            cout << a[i] << " ";

            i++;

            j++;

        }

    }

}

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

int main()

{

    int a[] = {1, 2, 3, 3, 4, 5, 5, 6};

    int b[] = {3, 3, 5};

      

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

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

    intersection(a, b, n, m);

}

Джава

// Java-код для поиска пересечения, когда
// элементы могут не отличаться

  

import java.io.*;

  

class GFG {

      
// Функция для поиска пересечения

static void intersection(int a[], int b[], int n, int m)

{

    int i = 0, j = 0;

      

    while (i < n && j < m) 

    {

                  

        if (a[i] > b[j]) 

        {

            j++;

        

                  

        else

        if (b[j] > a[i]) 

        {

            i++;

        

        else

        {

            // когда оба равны

            System.out.print(a[i] + " ");

            i++;

            j++;

        }

    }

}

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

    public static void main (String[] args) {

    int a[] = {1, 2, 3, 3, 4, 5, 5, 6};

    int b[] = {3, 3, 5};

      

    int n = a.length;

    int m = b.length;

    intersection(a, b, n, m);

    }

}

Python 3

# Python 3 код для поиска пересечения
# когда элементы могут не различаться

  
# Функция для поиска пересечения

def intersection(a, b, n, m):

  

    i = 0

    j = 0

      

    while (i < n and j < m) :

                  

        if (a[i] > b[j]) :

            j += 1

                  

        else:

            if (b[j] > a[i]) :

                i += 1

  

            else:

                # когда оба равны

                print(a[i], end = " ")

                i += 1

                j += 1

  
Код водителя

if __name__ =="__main__":

      

    a = [1, 2, 3, 3, 4, 5, 5, 6]

    b = [3, 3, 5]

      

    n = len(a)

    m = len(b)

    intersection(a, b, n, m)

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

C #

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

  

using System;

  

class GFG {

      
// Функция для поиска пересечения

static void intersection(int[] a, int[] b, int n, int m)

{

    int i = 0, j = 0;

      

    while (i < n && j < m) 

    {

                  

        if (a[i] > b[j]) 

        {

            j++;

        

                  

        else

        if (b[j] > a[i]) 

        {

            i++;

        

        else

        {

            // когда оба равны

            Console.Write(a[i] + " ");

            i++;

            j++;

        }

    }

}

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

    public static void Main () {

    int[] a = {1, 2, 3, 3, 4, 5, 5, 6};

    int[] b = {3, 3, 5};

      

    int n = a.Length;

    int m = b.Length;

    intersection(a, b, n, m);

    }

}
// этот код предоставлен Mukul Singh

PHP

<?php
// PHP-код для поиска пересечения, когда
// элементы могут не отличаться

  
// Функция для поиска пересечения

function intersection($a, $b, $n, $m)

{

    $i = 0; $j = 0;

      

    while ($i < $n && $j < $m

    {

                  

        if ($a[$i] > $b[$j]) 

        {

            $j++;

        

                  

        else

        if ($b[$j] > $a[$i]) 

        {

            $i++;

        

        else

        {

            // когда оба равны

            echo($a[$i] . " ");

            $i++;

            $j++;

        }

    }

}

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

$a = array(1, 2, 3, 3, 4, 5, 5, 6);

$b = array(3, 3, 5);

  

$n = sizeof($a);

$m = sizeof($b);

intersection($a, $b, $n, $m);

  
// Этот код добавлен
// Мукул Сингх
?>


Выход :

3 3 5

Спасибо Санни Кумар за предложенный выше метод.

Метод 4 (использовать хеширование)
Союз:
союз
1. Инициализируйте пустой хэш-набор hs .
2. Выполните итерацию по первому массиву и поместите каждый элемент первого массива в набор S.
3. Повторите процесс для второго массива.
4. Распечатайте набор hs .

пересечение
1. Инициализируйте пустой набор hs.
2. Выполните итерацию по первому массиву и поместите каждый элемент первого массива в набор S.
3. Для каждого элемента x второго массива сделайте следующее:
Поиск x в наборе hs. Если x присутствует, выведите его.

Временная сложность этого метода составляет Θ (m + n) в предположении, что операции поиска и вставки в хеш-таблицу занимают Θ (1) времени.

C ++

// Программа CPP для нахождения объединения и пересечения
// используя наборы
#include <bits/stdc++.h>

using namespace std;

  
// Печатает объединение arr1 [0..n1-1] и arr2 [0..n2-1]

void printUnion(int arr1[], int arr2[], int n1, int n2)

{

    set<int> hs;

  

    // Вставляем элементы arr1 [] для установки hs

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

        hs.insert(arr1[i]);

  

    // Вставляем элементы arr2 [] для установки hs

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

        hs.insert(arr2[i]);

  

    // Распечатать содержимое набора hs

    for (auto it = hs.begin(); it != hs.end(); it++)

        cout << *it << " ";

    cout << endl;

}

  
// Печатает пересечение arr1 [0..n1-1] и
// arr2 [0..n2-1]

void printIntersection(int arr1[], int arr2[],

                               int n1, int n2)

{

    set<int> hs;

  

    // Вставляем элементы arr1 [] для установки S

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

        hs.insert(arr1[i]);

  

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

  

        // Если элемент присутствует в наборе, то

        // вставляем его в вектор V

        if (hs.find(arr2[i]) != hs.end())

            cout << arr2[i] << " ";

}

  
// Программа для водителя

int main()

{

    int arr1[] = { 7, 1, 5, 2, 3, 6 };

    int arr2[] = { 3, 8, 6, 20, 7 };

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

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

    printUnion(arr1, arr2, n1, n2);

    printIntersection(arr1, arr2, n1, n2);

  

    return 0;

}

Джава

// Java-программа для поиска объединения и пересечения
// используя хеширование

import java.util.HashSet;

  

class Test

{   

    // Печатает объединение arr1 [0..m-1] и arr2 [0..n-1]

    static void printUnion(int arr1[], int arr2[])

    {

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

          

        for (int i = 0; i < arr1.length; i++) 

            hs.add(arr1[i]);        

        for (int i = 0; i < arr2.length; i++) 

            hs.add(arr2[i]);

        System.out.println(hs);        

    }

      

    // Печатает пересечение arr1 [0..m-1] и arr2 [0..n-1]

    static void printIntersection(int arr1[], int arr2[])

    {

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

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

          

        for (int i = 0; i < arr1.length; i++) 

            hs.add(arr1[i]);

          

        for (int i = 0; i < arr2.length; i++) 

            if (hs.contains(arr2[i]))

               System.out.print(arr2[i] + " ");

    }

      

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        int arr1[] = {7, 1, 5, 2, 3, 6};

        int arr2[] = {3, 8, 6, 20, 7};

  

        System.out.println("Union of two arrays is : ");

        printUnion(arr1, arr2);

          

        System.out.println("Intersection of two arrays is : ");

        printIntersection(arr1, arr2);        

    }

}

питон

# Программа Python для нахождения объединения и пересечения
# используя наборы

def printUnion(arr1, arr2, n1, n2):

    hs = set()

      

    # Вставить элементы arr1 [], чтобы установить hs

    for i in range(0, n1):

        hs.add(arr1[i])

          

    # Вставить элементы arr1 [], чтобы установить hs

    for i in range(0, n2):

        hs.add(arr2[i])

    print("Union:")

    for i in hs:

        print(i, end=" ")

    print("\n")

      

    # Печатает пересечение arr1 [0..n1-1] и

    # arr2 [0..n2-1]

def printIntersection(arr1, arr2, n1, n2):

    hs = set()

      

    # Вставьте элементы arr1 [], чтобы установить S

    for i in range(0, n1):

        hs.add(arr1[i])

    print("Intersection:")

    for i in range(0,n2):

          

        # Если элемент присутствует в наборе, то

        # подтолкнуть его к вектору V

        if arr2[i] in hs:

            print(arr2[i],end=" ")

              
# Драйверная программа

arr1 = [ 7, 1, 5, 2, 3, 6

arr2 = [ 3, 8, 6, 20, 7

n1 = len(arr1)

n2 = len(arr2)

printUnion(arr1, arr2, n1, n2) 
printIntersection(arr1, arr2, n1, n2) 

          
# Эта статья предоставлена Кумаром Суманом.

C #

// C # программа для поиска объединения и пересечения
// используя хеширование

using System;

using System.Linq;

using System.Collections.Generic;

  

class GFG

    // Печатает объединение arr1 [0..m-1] и arr2 [0..n-1]

    static void printUnion(int []arr1, int []arr2)

    {

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

          

        for (int i = 0; i < arr1.Length; i++) 

            hs.Add(arr1[i]);     

        for (int i = 0; i < arr2.Length; i++) 

            hs.Add(arr2[i]);

      

            Console.WriteLine(string.Join(", ", hs));     

    }

      

    // Печатает пересечение arr1 [0..m-1] и arr2 [0..n-1]

    static void printIntersection(int []arr1, int []arr2)

    {

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

          

        for (int i = 0; i < arr1.Length; i++) 

            hs.Add(arr1[i]);

          

        for (int i = 0; i < arr2.Length; i++) 

            if (hs.Contains(arr2[i]))

            Console.Write(arr2[i] + " ");

    }

      

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

    static void Main() 

    {

        int []arr1 = {7, 1, 5, 2, 3, 6};

        int []arr2 = {3, 8, 6, 20, 7};

  

        Console.WriteLine("Union of two arrays is : ");

        printUnion(arr1, arr2);

      

        Console.WriteLine("\nIntersection of two arrays is : ");

        printIntersection(arr1, arr2); 

    }

}

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


Этот метод предоставлен Анкуром Сингхом .

Выход:

Union of two arrays is : 
[1, 2, 3, 20, 5, 6, 7, 8]
Intersection of two arrays is : 
3 6 7 

Метод 5 (Вид техники хеширования без использования каких-либо предопределенных коллекций Java)
1. Начать массив размером m + n
2. Заполните первое значение массива в результирующем массиве, выполнив хеширование (чтобы найти подходящую позицию)
3. Повторите для второго массива
4. Во время хеширования, если происходит столкновение, рекурсивно увеличивайте позицию

Джава

// Java-программа для поиска объединения и пересечения
// используя похожую технику хеширования
// без использования предопределенных коллекций Java
// Сложность времени в лучшем случае & avg case = O (m + n)
// В худшем случае = O (nlogn)

  
// package com.arrays.math;

  

public class UnsortedIntersectionUnion {

  

        // Печатает пересечение arr1 [0..n1-1] и

        // arr2 [0..n2-1]

    public void findPosition(int a[], int b[]) {

        int v = (a.length + b.length);

        int ans[] = new int[v];

  

        int zero1 = 0;

        int zero2 = 0;

  

        System.out.print("Intersection : ");

        // Итерация первого массива

        for (int i = 0; i < a.length; i++)

            zero1 = iterateArray(a, v, ans, i);

  

        // Итерация второго массива

        for (int j = 0; j < b.length; j++)

            zero2 = iterateArray(b, v, ans, j);

  

        int zero = zero1 + zero2;

        placeZeros(v, ans, zero);

        printUnion(v, ans, zero);

  

    }

      

    // Печатает объединение arr1 [0..n1-1] и arr2 [0..n2-1]

    private void printUnion(int v, int[] ans, int zero) {

        int zero1 = 0;

        System.out.print("\nUnion : ");

        for (int i = 0; i < v; i++) {

            if ((zero == 0 && ans[i] == 0) || (ans[i] == 0 && zero1 > 0))

                continue;

            if (ans[i] == 0)

                zero1++;

            System.out.print(ans[i] + ",");

        }

    }

  

    private void placeZeros(int v, int[] ans, int zero) {

        if (zero == 2) {

            System.out.println("0");

            int d[] = { 0 };

            placeValue(d, ans, 0, 0, v);

        }

        if (zero == 1) {

            int d[] = { 0 };

            placeValue(d, ans, 0, 0, v);

        }

    }

  

    // Функция для создания массива

    private int iterateArray(int[] a, int v, int[] ans, int i) {

        if (a[i] != 0) {

            int p = a[i] % v;

            placeValue(a, ans, i, p, v);

        } else

            return 1;

        return 0;

    }

  

    private void placeValue(int[] a, int[] ans, int i, int p, int v) {

        p = p % v;

        if (ans[p] == 0)

            ans[p] = a[i];

        else {

            if (ans[p] == a[i])

                System.out.print(a[i] + ",");

            else {

                  

                // Хеширование столкновения произошло приращением позиции и выполнением рекурсивного вызова

                p = p + 1;

                placeValue(a, ans, i, p, v);

            }

        }

    }

  

    public static void main(String args[]) {

        int a[] = { 7, 1, 5, 2, 3, 6 };

        int b[] = { 3, 8, 6, 20, 7 };

  

        UnsortedIntersectionUnion uiu = new UnsortedIntersectionUnion();

        uiu.findPosition(a, b);

    }

}
// Этот код предоставлен Моханакришнан С.

python3

# Python3 программа для поиска объединения и пересечения
# используя похожую технику хеширования
# без использования каких-либо предопределенных коллекций Java
# Сложность по времени в лучшем случае & avg case = O (m + n)
# В худшем случае = O (nlogn)

  

  
# Печатает пересечение arr1 [0..n1-1] и
# arr2 [0..n2-1]

def findPosition(a, b):

    v = len(a) + len(b);

    ans = [0]*v;

    zero1 = zero2 = 0;

    print("Intersection :",end=" ");

      

    # Итерировать первый массив

    for i in range(len(a)):

        zero1 = iterateArray(a, v, ans, i);

      

    # Итерировать второй массив

    for j in range(len(b)):

        zero2 = iterateArray(b, v, ans, j);

      

    zero = zero1 + zero2;

    placeZeros(v, ans, zero);

    printUnion(v, ans, zero);

      
# Выводит объединение arr1 [0..n1-1] и arr2 [0..n2-1]

def printUnion(v, ans,zero):

    zero1 = 0;

    print("\nUnion :",end=" ");

    for i in range(v):

        if ((zero == 0 and ans[i] == 0) or

            (ans[i] == 0 and zero1 > 0)):

            continue;

        if (ans[i] == 0):

            zero1+=1;

        print(ans[i],end=",");

  

def placeZeros(v, ans, zero):

    if (zero == 2):

        print("0");

        d = [0];

        placeValue(d, ans, 0, 0, v);

    if (zero == 1):

        d=[0];

        placeValue(d, ans, 0, 0, v);

  
# Функция для создания массива

def iterateArray(a,v,ans,i):

    if (a[i] != 0):

        p = a[i] % v;

        placeValue(a, ans, i, p, v);

    else:

        return 1;

      

    return 0;

  

def placeValue(a,ans,i,p,v):

    p = p % v;

    if (ans[p] == 0):

        ans[p] = a[i];

    else:

        if (ans[p] == a[i]):

            print(a[i],end=",");

        else:

            # Хэширование столкновения произошло приращением

            # позиционируй и делай рекурсивный вызов

            p = p + 1;

            placeValue(a, ans, i, p, v);

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

a = [ 7, 1, 5, 2, 3, 6 ];

b = [ 3, 8, 6, 20, 7 ];

findPosition(a, b);

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

C #

// C # программа для поиска объединения и пересечения
// используя похожую технику хеширования
// без использования предопределенных коллекций Java
// Сложность времени в лучшем случае & avg case = O (m + n)
// В худшем случае = O (nlogn)

  
// package com.arrays.math;

using System;

class UnsortedIntersectionUnion 

{

  

        // Печатает пересечение arr1 [0..n1-1] и

        // arr2 [0..n2-1]

    public void findPosition(int []a, int []b)

    {

        int v = (a.Length + b.Length);

        int []ans = new int[v];

  

        int zero1 = 0;

        int zero2 = 0;

  

        Console.Write("Intersection : ");

          

        // Итерация первого массива

        for (int i = 0; i < a.Length; i++)

            zero1 = iterateArray(a, v, ans, i);

  

        // Итерация второго массива

        for (int j = 0; j < b.Length; j++)

            zero2 = iterateArray(b, v, ans, j);

  

        int zero = zero1 + zero2;

        placeZeros(v, ans, zero);

        printUnion(v, ans, zero);

  

    }

      

    // Печатает объединение arr1 [0..n1-1]

    // и arr2 [0..n2-1]

    private void printUnion(int v, int[] ans, int zero)

    {

        int zero1 = 0;

        Console.Write("\nUnion : ");

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

        {

            if ((zero == 0 && ans[i] == 0) || 

                    (ans[i] == 0 && zero1 > 0))

                continue;

            if (ans[i] == 0)

                zero1++;

            Console.Write(ans[i] + ",");

        }

    }

  

    private void placeZeros(int v, int[] ans, int zero)

    {

        if (zero == 2) 

        {

            Console.WriteLine("0");

            int []d = { 0 };

            placeValue(d, ans, 0, 0, v);

        }

        if (zero == 1) 

        {

            int []d = { 0 };

            placeValue(d, ans, 0, 0, v);

        }

    }

  

    // Функция для создания массива

    private int iterateArray(int[] a, int v, 

                            int[] ans, int i)

    {

        if (a[i] != 0) 

        {

            int p = a[i] % v;

            placeValue(a, ans, i, p, v);

        } else

            return 1;

        return 0;

    }

  

    private void placeValue(int[] a, int[] ans, 

                                int i, int p, int v) 

    {

        p = p % v;

        if (ans[p] == 0)

            ans[p] = a[i];

        else {

            if (ans[p] == a[i])

                Console.Write(a[i] + ",");

            else

            {

                  

                // Хэширование столкновения произошло с приращением

                // позиционируем и делаем рекурсивный вызов

                p = p + 1;

                placeValue(a, ans, i, p, v);

            }

        }

    }

  

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

    public static void Main() 

    {

        int []a = { 7, 1, 5, 2, 3, 6 };

        int []b = { 3, 8, 6, 20, 7 };

  

        UnsortedIntersectionUnion uiu = new UnsortedIntersectionUnion();

        uiu.findPosition(a, b);

    }

}

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


Выход:

Intersection : 3,6,7,
Union : 1,2,3,5,6,7,8,20,

Смотрите следующий пост для отсортированных массивов.
Найти объединение и пересечение двух отсортированных массивов

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

# Программа Python для нахождения объединения и пересечения
# используя наборы

def printUnion(arr1,arr2,n1,n2):

    hs=set()

    # Вставить элементы arr1 [], чтобы установить hs

    for i in range(0,n1):

        hs.add(arr1[i])

    # Вставить элементы arr1 [], чтобы установить hs

    for i in range(0,n2):

        hs.add(arr2[i])

    print("Union:")

    for i in hs:

        print(i,end=" ")

    print("\n")

    # Печатает пересечение arr1 [0..n1-1] и

    # arr2 [0..n2-1]

def printIntersection(arr1,arr2,n1,n2):

    hs=set()

    # Вставьте элементы arr1 [], чтобы установить S

    for i in range(0,n1):

        hs.add(arr1[i])

    print("Intersection:")

    for i in range(0,n2):

        # Если элемент присутствует в наборе, то

        # подтолкнуть его к вектору V

        if arr2[i] in hs:

            print(arr2[i],end=" ")

# Драйверная программа

arr1 = [ 7, 1, 5, 2, 3, 6

arr2 = [ 3, 8, 6, 20, 7

n1=len(arr1)

n2=len(arr2)

printUnion(arr1, arr2, n1, n2) 
printIntersection(arr1, arr2, n1, n2) 

          
# Эта статья предоставлена Кумаром Суманом.

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

Найти объединение и пересечение двух несортированных массивов

0.00 (0%) 0 votes