Рубрики

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

Учитывая два отсортированных массива, найдите их объединение и пересечение.

Пример:

Input : arr1[] = {1, 3, 4, 5, 7}
        arr2[] = {2, 3, 5, 6} 
Output : Union : {1, 2, 3, 4, 5, 6, 7} 
         Intersection : {3, 5}

Input : arr1[] = {2, 5, 6}
        arr2[] = {4, 6, 8, 10} 
Output : Union : {2, 4, 5, 6, 8, 10} 
         Intersection : {6}

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Союз массивов arr1 [] и arr2 []

Чтобы найти объединение двух отсортированных массивов, выполните следующую процедуру слияния:

1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
3) If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
4) If both are same then print any of them and increment both i and j.
5) Print remaining elements of the larger array.

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

C ++

// C ++ программа для поиска объединения
// два отсортированных массива
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция выводит объединение arr1 [] и arr2 []

   m - количество элементов в arr1 []

   n - количество элементов в arr2 [] * /

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

{

  int i = 0, j = 0;

  while (i < m && j < n)

  {

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

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

      

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

       cout << arr2[j++] << " ";

      

    else

    {

       cout << arr2[j++] << " ";

       i++;

    }

  }

  

  / * Печать оставшихся элементов большего массива * /

  while(i < m)

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

  

  while(j < n)

    cout << arr2[j++] << " ";

}

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

int main()

{

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

  int arr2[] = {2, 3, 5, 7};

    

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

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

    

  // вызов функции

  printUnion(arr1, arr2, m, n);

  

  return 0;

}

С

// C программа для поиска объединения
// два отсортированных массива
#include<stdio.h>

  
/ * Функция выводит объединение arr1 [] и arr2 []

   m - количество элементов в arr1 []

   n - количество элементов в arr2 [] * /

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

{

  int i = 0, j = 0;

  while (i < m && j < n)

  {

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

      printf(" %d ", arr1[i++]);

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

      printf(" %d ", arr2[j++]);

    else

    {

      printf(" %d ", arr2[j++]);

      i++;

    }

  }

  

  / * Печать оставшихся элементов большего массива * /

  while(i < m)

   printf(" %d ", arr1[i++]);

  while(j < n)

   printf(" %d ", arr2[j++]);

}

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

int main()

{

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

  int arr2[] = {2, 3, 5, 7};

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

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

  printUnion(arr1, arr2, m, n);

  getchar();

  return 0;

}

Джава

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

  

class FindUnion

{

    / * Функция выводит объединение arr1 [] и arr2 []

    m - количество элементов в arr1 []

    n - количество элементов в arr2 [] * /

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

    {

      int i = 0, j = 0;

      while (i < m && j < n)

      {

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

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

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

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

        else

        {

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

          i++;

        }

      }

       

      / * Печать оставшихся элементов

         больший массив * /

      while(i < m)

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

      while(j < n)

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

         

      return 0;   

    }

      

    public static void main(String args[])

    {

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

        int arr2[] = {2, 3, 5, 7};

        int m = arr1.length;

        int n = arr2.length;

        printUnion(arr1, arr2, m, n);

    }

}

питон

# Программа Python, чтобы найти объединение
# два отсортированных массива
# Функция печатает объединение arr1 [] и arr2 []
# m - количество элементов в arr1 []
# n - количество элементов в arr2 []

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

    i,j = 0,0

    while i < m and j < n:

        if arr1[i] < arr2[j]:

            print(arr1[i])

            i += 1

        elif arr2[j] < arr1[i]:

            print(arr2[j])

            j+= 1

        else:

            print(arr2[j])

            j += 1

            i += 1

  

    # Распечатать оставшиеся элементы большего массива

    while i < m:

        print(arr1[i])

        i += 1

  

    while j < n:

        print(arr2[j])

        j += 1

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

arr1 = [1, 2, 4, 5, 6]

arr2 = [2, 3, 5, 7]

m = len(arr1)

n = len(arr2)

printUnion(arr1, arr2, m, n)

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

C #

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

  

using System;

  

class GFG

{

    / * Функция выводит объединение arr1 [] и arr2 []

    m - количество элементов в arr1 []

    n - количество элементов в arr2 [] * /

    static int printUnion(int []arr1,

                   int []arr2, int m, int n)

    {

    int i = 0, j = 0;

  

    while (i < m && j < n)

    {

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

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

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

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

        else

        {

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

            i++;

        }

    }

      

    / * Печать оставшихся элементов

        больший массив * /

    while (i < m)

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

    while (j < n)

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

          

    return 0; 

    }

      

    public static void Main()

    {

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

        int []arr2 = {2, 3, 5, 7};

        int m = arr1.Length;

        int n = arr2.Length;

          

        printUnion(arr1, arr2, m, n);

    

}

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

PHP

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

  
/ * Функция печатает объединение

  arr1 [] и arr2 [] m - это

  количество элементов в arr1 []

  n - количество элементов

  в arr2 [] * /

function printUnion($arr1, $arr2,

                         $m, $n)

{

    $i = 0; $j = 0;

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

    {

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

            echo($arr1[$i++] . " ");

          

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

            echo($arr2[$j++] . " ");

          

        else

        {

            echo($arr2[$j++] . " ");

            $i++;

        }

    }

      

    // Печать оставшихся элементов

    // большего массива

    while($i < $m)

        echo($arr1[$i++] . " ");

      

    while($j < $n)

        echo($arr2[$j++] . " ");

}

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

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

$arr2 = array(2, 3, 5, 7);

  

$m = sizeof($arr1);

$n = sizeof($arr2);

  
// вызов функции

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

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

Выход:

1 2 3 4 5 6 7 

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

Обработка дубликатов в любом массиве. Приведенный выше код не обрабатывает дубликаты ни в одном массиве. Чтобы обработать дубликаты, просто проверьте для каждого элемента, равны ли соседние элементы.
Ниже приведена реализация этого подхода.

Джава

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

class FindUnion

{

      

    static void UnionArray(int arr1[], 

                           int arr2[])

    {

        // Взятие максимального элемента, присутствующего в любом массиве

        int m = arr1[arr1.length - 1];

        int n = arr2[arr2.length - 1];

          

        int ans = 0;

          

        if(m > n)

        {

            ans = m;

        }

        else

        ans = n;

          

        // Поиск элементов из первого массива

        // (только без дубликатов). С помощью

        // еще один массив для хранения объединения

        // элементы обоих массивов

        // Предполагается наличие максимального элемента

        // в массиве не более 10 ^ 7

        int newtable[] = new int[ans + 1];

          

        // Первый элемент всегда

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

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

          

        // Увеличиваем счетчик первого элемента

        // в соответствующем индексе в newtable

        ++newtable[arr1[0]];

          

        // Начинаем обход первого

        // массив от 1-го индекса до последнего

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

        {

            // Проверка наличия текущего элемента

            // не равен его предыдущему элементу

            if(arr1[i] != arr1[i - 1])

            {

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

                ++newtable[arr1[i]];

            }

        }

          

        // Нахождение только не общего

        // элементы из 2-го массива

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

        {

            // Проверяя, уже

            // присутствует в newtable или нет

            if(newtable[arr2[j]] == 0)

            {

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

                ++newtable[arr2[j]];

            }

        }

    }

      

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

    public static void main(String args[])

    {

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

        int arr2[] = {2, 3, 4, 5};

          

        UnionArray(arr1, arr2);

    }

}

python3

# Python3 программа для поиска объединения двух
# отсортированные массивы (обработка дубликатов)

def UnionArray(arr1, arr2): 

      

    # Взятие максимального элемента, присутствующего в любом массиве

    m = arr1[-1

    n = arr2[-1

    ans = 0

          

    if m > n: 

        ans =

    else:

        ans =

          

    # Поиск элементов из первого массива

    # (только без дубликатов). С помощью

    # другой массив для хранения объединения

    # элементы обоих массивов

    # Предполагая наличие максимального элемента

    # в массиве не более 10 ^ 7

    newtable = [0] * (ans + 1

          

    # Первый элемент всегда

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

    print(arr1[0], end = " "

          

    # Увеличение числа первых элементов

    # в соответствующем индексе в newtable

    newtable[arr1[0]] += 1

          

    # Начало прохождения первого

    # массив от первого индекса до последнего

    for i in range(1, len(arr1)): 

          

        # Проверка наличия текущего элемента

        # не равен его предыдущему элементу

        if arr1[i] != arr1[i - 1]: 

              

            print(arr1[i], end = " "

            newtable[arr1[i]] += 1

              

    # Нахождение только необычного

    # элементы из 2-го массива

    for j in range(0, len(arr2)): 

          

        # Проверяя, уже ли это

        # присутствует в newtable или нет

        if newtable[arr2[j]] == 0

              

            print(arr2[j], end = " "

            newtable[arr2[j]] += 1

      
Код водителя

if __name__ == "__main__"

      

    arr1 = [1, 2, 2, 2, 3]

    arr2 = [2, 3, 4, 5]

          

    UnionArray(arr1, arr2) 

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

C #

// C # программа для поиска объединения двух
// отсортированные массивы (обработка дубликатов)

using System;

  

class GFG {

      

    static void UnionArray(int []arr1, 

                           int []arr2)

    {

          

        // Принимая макс элемент присутствует

        // в любом массиве

        int m = arr1[arr1.Length - 1];

        int n = arr2[arr2.Length - 1];

          

        int ans = 0;

          

        if(m > n)

            ans = m;

        else

            ans = n;

          

        // Поиск элементов из первого массива

        // (только без дубликатов). С помощью

        // еще один массив для хранения объединения

        // элементы обоих массивов

        // Предполагается наличие максимального элемента

        // в массиве не более 10 ^ 7

        int []newtable = new int[ans + 1];

          

        // Первый элемент всегда

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

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

          

        // Увеличиваем первый элемент

        // считать в соответствующем

        // индекс в newtable

        ++newtable[arr1[0]];

          

        // Начинаем обход первого

        // массив от 1-го индекса до последнего

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

        {

            // Проверка текущей

            // элемент не равен

            // это предыдущий элемент

            if(arr1[i] != arr1[i - 1])

            {

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

                ++newtable[arr1[i]];

            }

        }

          

        // Нахождение только не общего

        // элементы из 2-го массива

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

        {

            // Проверяя, уже

            // присутствует в newtable или нет

            if(newtable[arr2[j]] == 0)

            {

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

                ++newtable[arr2[j]];

            }

        }

    }

      

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

    public static void Main()

    {

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

        int []arr2 = {2, 3, 4, 5};

          

        UnionArray(arr1, arr2);

    }

}

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


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

Пересечение массивов arr1 [] и arr2 []

Чтобы найти пересечение 2 отсортированных массивов, используйте следующий подход:

1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.

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

C ++

// C ++ программа для поиска пересечения
// два отсортированных массива
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция печатает пересечение arr1 [] и arr2 []
m - количество элементов в arr1 []
n - количество элементов в arr2 [] * /

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

{

  int i = 0, j = 0;

  while (i < m && j < n)

  {

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

       i++;

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

       j++;

    else / * если arr1 [i] == arr2 [j] * /

    {

       cout << arr2[j] << " ";

       i++;

       j++;

    }

  }

}

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

int main()

{

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

  int arr2[] = {2, 3, 5, 7};

    

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

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

    

  // вызов функции

  printIntersection(arr1, arr2, m, n);

  

  return 0;

}

С

// C программа для поиска пересечения
// два отсортированных массива
#include<stdio.h>

  
/ * Функция печатает пересечение arr1 [] и arr2 []

   m - количество элементов в arr1 []

   n - количество элементов в arr2 [] * /

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

{

  int i = 0, j = 0;

  while (i < m && j < n)

  {

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

      i++;

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

      j++;

    else / * если arr1 [i] == arr2 [j] * /

    {

      printf(" %d ", arr2[j++]);

      i++;

    }

  }

}

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

int main()

{

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

  int arr2[] = {2, 3, 5, 7};

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

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

  printIntersection(arr1, arr2, m, n);

  getchar();

  return 0;

}

Джава

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

  

class FindIntersection

{

    / * Функция печатает пересечение arr1 [] и arr2 []

       m - количество элементов в arr1 []

       n - количество элементов в arr2 [] * /

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

    {

      int i = 0, j = 0;

      while (i < m && j < n)

      {

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

          i++;

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

          j++;

        else 

        {

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

          i++;

        }

      }

    }

      

    public static void main(String args[])

    {

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

        int arr2[] = {2, 3, 5, 7};

        int m = arr1.length;

        int n = arr2.length;

        printIntersection(arr1, arr2, m, n);

    }

}

питон

# Программа Python для поиска пересечения
# два отсортированных массива
# Функция печатает пересечение arr1 [] и arr2 []
# m - количество элементов в arr1 []
# n - количество элементов в arr2 []

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

    i,j = 0,0

    while i < m and j < n:

        if arr1[i] < arr2[j]:

            i += 1

        elif arr2[j] < arr1[i]:

            j+= 1

        else:

            print(arr2[j])

            j += 1

            i += 1

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

arr1 = [1, 2, 4, 5, 6]

arr2 = [2, 3, 5, 7]

m = len(arr1)

n = len(arr2)

printIntersection(arr1, arr2, m, n)

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

C #

// C # программа для поиска пересечения
// два отсортированных массива

  

using System;

  

class GFG

{

      

      

    / * Функция печатает пересечение arr1 []

    и arr2 [] m - количество элементов в arr1 []

    n - количество элементов в arr2 [] * /

    static void printIntersection(int []arr1,

                        int []arr2, int m, int n)

    {

        int i = 0, j = 0;

          

        while (i < m && j < n)

        {

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

                i++;

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

                j++;

            else

            {

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

                i++;

            }

        }

    }

      

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

    public static void Main()

    {

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

        int []arr2 = {2, 3, 5, 7};

        int m = arr1.Length;

        int n = arr2.Length;

          

        printIntersection(arr1, arr2, m, n);

    

}

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

PHP

<?php
// PHP программа для поиска пересечения
// два отсортированных массива

  
/ * Функция печатает пересечение

   из arr1 [] и arr2 [] m является

   количество элементов в arr1 []

   n - количество элементов

   в arr2 [] * /

function printIntersection($arr1, $arr2,

                                $m, $n)

{

    $i = 0 ;

    $j = 0;

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

    {

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

            $i++;

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

            $j++;

              

        / * если arr1 [i] == arr2 [j] * /

        else 

        {

            echo $arr2[$j] , " ";

            $i++;

            $j++;

        }

    }

}

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

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

$arr2 = array(2, 3, 5, 7);

  

$m = count($arr1);

$n = count($arr2);

  
// вызов функции

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

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


Выход:

2 5

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

Другой подход, который полезен, когда разница между размерами двух данных массивов является существенной.

Идея состоит в том, чтобы выполнить итерацию по более короткому массиву и выполнить бинарный поиск для каждого элемента короткого массива в большом массиве (обратите внимание, что массивы отсортированы). Временная сложность этого решения составляет O (min (mLogn, nLogm)). Это решение работает лучше, чем описанный выше подход, когда отношение большей длины к меньшей больше логарифмического порядка.

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

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

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

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

0.00 (0%) 0 votes