Unión e intersección de dos arrays ordenadas

Posted on by Rudeus Greyrat

Dadas dos arrays ordenadas, encuentre su unión e intersección.
Ejemplo:

Entrada: arr1[] = {1, 3, 4, 5, 7}
        arr2[] = {2, 3, 5, 6} 
Salida: Unión: {1, 2, 3, 4, 5, 6, 7} 
         Intersección : {3, 5}

Entrada: arr1[] = {2, 5, 6}
        arr2[] = {4, 6, 8, 10} 
Salida: Unión: {2, 4, 5, 6, 8, 10} 
         Intersección: {6}

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Unión de arreglos arr1[] y arr2[]

Para encontrar la unión de dos arrays ordenadas, siga el siguiente procedimiento de combinación: 

1) Use dos variables de índice i y j, valores iniciales i = 0, j = 0 
2) Si arr1[i] es menor que arr2[j], imprima arr1[i] e incremente i. 
3) Si arr1[i] es mayor que arr2[j], imprima arr2[j] e incremente j. 
4) Si ambos son iguales, imprima cualquiera de ellos e incremente tanto i como j. 
5) Imprima los elementos restantes de la array más grande.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to find union of
// two sorted arrays
#include <bits/stdc++.h>
using namespace std;
 
/* Function prints union of arr1[] and arr2[]
   m is the number of elements in arr1[]
   n is the number of elements in arr2[] */
void 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++;
        }
    }
 
    /* Print remaining elements of the larger array */
    while (i < m)
        cout << arr1[i++] << " ";
 
    while (j < n)
        cout << arr2[j++] << " ";
}
 
/* Driver program to test above function */
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]);
 
    // Function calling
    printUnion(arr1, arr2, m, n);
 
    return 0;
}

C

// C program to find union of
// two sorted arrays
#include <stdio.h>
 
/* Function prints union of arr1[] and arr2[]
   m is the number of elements in arr1[]
   n is the number of elements in arr2[] */
void 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++;
        }
    }
 
    /* Print remaining elements of the larger array */
    while (i < m)
        printf(" %d ", arr1[i++]);
    while (j < n)
        printf(" %d ", arr2[j++]);
}
 
/* Driver program to test above function */
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

// Java program to find union of
// two sorted arrays
 
class FindUnion {
    /* Function prints union of arr1[] and arr2[]
    m is the number of elements in arr1[]
    n is the number of elements in 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++;
            }
        }
 
        /* Print remaining elements of
         the larger array */
        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);
    }
}

Python3

# Python program to find union of
# two sorted arrays
# Function prints union of arr1[] and arr2[]
# m is the number of elements in arr1[]
# n is the number of elements in 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],end=" ")
            i += 1
        elif arr2[j] < arr1[i]:
            print(arr2[j],end=" ")
            j+= 1
        else:
            print(arr2[j],end=" ")
            j += 1
            i += 1
 
    # Print remaining elements of the larger array
    while i < m:
        print(arr1[i],end=" ")
        i += 1
 
    while j < n:
        print(arr2[j],end=" ")
        j += 1
 
# Driver program to test above function
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
m = len(arr1)
n = len(arr2)
printUnion(arr1, arr2, m, n)
 
# This code is contributed by Pratik Chhajer

C#

// C# program to find union of
// two sorted arrays
 
using System;
 
class GFG {
    /* Function prints union of arr1[] and arr2[]
    m is the number of elements in arr1[]
    n is the number of elements in 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++;
            }
        }
 
        /* Print remaining elements of
        the larger array */
        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);
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP program to find union of
// two sorted arrays
 
/* Function prints union of
  arr1[] and arr2[] m is the
  number of elements in arr1[]
  n is the number of elements
  in 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++;
        }
    }
     
    // Print remaining elements
    // of the larger array
    while($i < $m)
        echo($arr1[$i++] . " ");
     
    while($j < $n)
        echo($arr2[$j++] . " ");
}
 
// Driver Code
$arr1 = array(1, 2, 4, 5, 6);
$arr2 = array(2, 3, 5, 7);
 
$m = sizeof($arr1);
$n = sizeof($arr2);
 
// Function calling
printUnion($arr1, $arr2, $m, $n);
 
// This code is contributed by Ajit.
?>

JavaScript

<script>
// JavaScript program to find union of
// two sorted arrays
 
    /* Function prints union of arr1[] and arr2[]
    m is the number of elements in arr1[]
    n is the number of elements in arr2[] */
    function printUnion( arr1,  arr2,  m,  n)
    {
        var i = 0, j = 0;
        while (i < m && j < n) {
            if (arr1[i] < arr2[j])
                document.write(arr1[i++] + " ");
            else if (arr2[j] < arr1[i])
                document.write(arr2[j++] + " ");
            else {
                document.write(arr2[j++] + " ");
                i++;
            }
        }
 
        /* Print remaining elements of
        the larger array */
        while (i < m)
            document.write(arr1[i++] + " ");
        while (j < n)
            document.write(arr2[j++] + " ");
 
        return 0;
    }
 
        var arr1 = [ 1, 2, 4, 5, 6 ];
        var arr2 = [ 2, 3, 5, 7 ];
        var m = arr1.length;
        var n = arr2.length;
        printUnion(arr1, arr2, m, n);
         
// this code is contributed by shivanisinghss2110
</script>
Producción

1 2 3 4 5 6 7

Complejidad temporal: O(m + n)
Espacio auxiliar: O(1)

Manejo de duplicados en cualquiera de las arrays: el código anterior no maneja duplicados en ninguna de las arrays. Para manejar los duplicados, simplemente verifique para cada elemento si los elementos adyacentes son iguales. 

A continuación se muestra la implementación de este enfoque. 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
static void UnionArray(int arr1[], int arr2[], int l1,
                       int l2)
{
    // Taking max element present in either array
    int m = arr1[l1 - 1];
    int n = arr2[l2 - 1];
    int ans = 0;
    if (m > n)
        ans = m;
    else
        ans = n;
 
    // Finding elements from 1st array (non duplicates
    // only). Using another array for storing union elements
    // of both arrays Assuming max element present in array
    // is not more than 10^7
    int newtable[ans + 1];
    memset(newtable, 0, sizeof(newtable));
    // First element is always present in final answer
    cout << arr1[0] << " ";
 
    // Incrementing the First element's count in it's
    // corresponding index in newtable
    ++newtable[arr1[0]];
 
    // Starting traversing the first array from 1st index
    // till last
    for (int i = 1; i < l1; i++) {
        // Checking whether current element is not equal to
        // it's previous element
        if (arr1[i] != arr1[i - 1]) {
            cout << arr1[i] << " ";
            ++newtable[arr1[i]];
        }
    }
 
    // Finding only non common elements from 2nd array
    for (int j = 0; j < l2; j++) {
        // By checking whether it's already resent in
        // newtable or not
        if (newtable[arr2[j]] == 0) {
            cout << arr2[j] << " ";
            ++newtable[arr2[j]];
        }
    }
}
 
// Driver Code
int main()
{
    int arr1[] = { 1, 2, 2, 2, 3 };
    int arr2[] = { 2, 3, 4, 5 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
 
    UnionArray(arr1, arr2, n, m);
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

C

// C program for the above approach
#include <stdio.h>
#include <string.h>
 
static void UnionArray(int arr1[], int arr2[], int l1,
                       int l2)
{
    // Taking max element present in either array
    int m = arr1[l1 - 1];
    int n = arr2[l2 - 1];
    int ans = 0;
    if (m > n)
        ans = m;
    else
        ans = n;
 
    // Finding elements from 1st array (non duplicates
    // only). Using another array for storing union elements
    // of both arrays Assuming max element present in array
    // is not more than 10^7
    int newtable[ans + 1];
    for (int i = 0; i < ans + 1; i++)
        newtable[i] = 0;
    // First element is always present in final answer
    printf("%d ", arr1[0]);
 
    // Incrementing the First element's count in it's
    // corresponding index in newtable
    ++newtable[arr1[0]];
 
    // Starting traversing the first array from 1st index
    // till last
    for (int i = 1; i < l1; i++) {
        // Checking whether current element is not equal to
        // it's previous element
        if (arr1[i] != arr1[i - 1]) {
            printf("%d ", arr1[i]);
            ++newtable[arr1[i]];
        }
    }
 
    // Finding only non common elements from 2nd array
    for (int j = 0; j < l2; j++) {
        // By checking whether it's already resent in
        // newtable or not
        if (newtable[arr2[j]] == 0) {
            printf("%d ", arr2[j]);
            ++newtable[arr2[j]];
        }
    }
}
 
// Driver Code
int main()
{
    int arr1[] = { 1, 2, 2, 2, 3 };
    int arr2[] = { 2, 3, 4, 5 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
 
    UnionArray(arr1, arr2, n, m);
 
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

Java

// Java program to find union of two
// sorted arrays (Handling Duplicates)
class FindUnion {
 
    static void UnionArray(int arr1[],
                           int arr2[])
    {
        // Taking max element present in either array
        int m = arr1[arr1.length - 1];
        int n = arr2[arr2.length - 1];
 
        int ans = 0;
 
        if (m > n) {
            ans = m;
        }
        else
            ans = n;
 
        // Finding elements from 1st array
        // (non duplicates only). Using
        // another array for storing union
        // elements of both arrays
        // Assuming max element present
        // in array is not more than 10^7
        int newtable[] = new int[ans + 1];
 
        // First element is always
        // present in final answer
        System.out.print(arr1[0] + " ");
 
        // Incrementing the First element's count
        // in it's corresponding index in newtable
        ++newtable[arr1[0]];
 
        // Starting traversing the first
        // array from 1st index till last
        for (int i = 1; i < arr1.length; i++) {
            // Checking whether current element
            // is not equal to it's previous element
            if (arr1[i] != arr1[i - 1]) {
                System.out.print(arr1[i] + " ");
                ++newtable[arr1[i]];
            }
        }
 
        // Finding only non common
        // elements from 2nd array
        for (int j = 0; j < arr2.length; j++) {
            // By checking whether it's already
            // present in newtable or not
            if (newtable[arr2[j]] == 0) {
                System.out.print(arr2[j] + " ");
                ++newtable[arr2[j]];
            }
        }
    }
 
    // Driver Code
    public static void main(String args[])
    {
        int arr1[] = { 1, 2, 2, 2, 3 };
        int arr2[] = { 2, 3, 4, 5 };
 
        UnionArray(arr1, arr2);
    }
}

Python3

# Python3 program to find union of two
# sorted arrays (Handling Duplicates)
def union_array(arr1, arr2):
    m = len(arr1)
    n = len(arr2)
    i = 0
    j = 0
     
    # keep track of last element to avoid duplicates
    prev = None
     
    while i < m and j < n:
        if arr1[i] < arr2[j]:
            if arr1[i] != prev:
                print(arr1[i], end=' ')
                prev = arr1[i]
            i += 1
        elif arr1[i] > arr2[j]:
            if arr2[j] != prev:
                print(arr2[j], end=' ')
                prev = arr2[j]
            j += 1
        else:
            if arr1[i] != prev:
                print(arr1[i], end=' ')
                prev = arr1[i]
            i += 1
            j += 1
             
    while i < m:
        if arr1[i] != prev:
            print(arr1[i], end=' ')
            prev = arr1[i]
        i += 1
 
    while j < n:
        if arr2[j] != prev:
            print(arr2[j], end=' ')
            prev = arr2[j]
        j += 1
     
# Driver Code
if __name__ == "__main__":
    arr1 = [1, 2, 2, 2, 3]
    arr2 = [2, 3, 4, 5]
         
    union_array(arr1, arr2)
 
# This code is contributed by Sanjay Kumar

C#

// C# program to find union of two
// sorted arrays (Handling Duplicates)
using System;
 
class GFG {
 
    static void UnionArray(int[] arr1,
                           int[] arr2)
    {
 
        // Taking max element present
        // in either array
        int m = arr1[arr1.Length - 1];
        int n = arr2[arr2.Length - 1];
 
        int ans = 0;
 
        if (m > n)
            ans = m;
        else
            ans = n;
 
        // Finding elements from 1st array
        // (non duplicates only). Using
        // another array for storing union
        // elements of both arrays
        // Assuming max element present
        // in array is not more than 10^7
        int[] newtable = new int[ans + 1];
 
        // First element is always
        // present in final answer
        Console.Write(arr1[0] + " ");
 
        // Incrementing the First element's
        // count in it's corresponding
        // index in newtable
        ++newtable[arr1[0]];
 
        // Starting traversing the first
        // array from 1st index till last
        for (int i = 1; i < arr1.Length; i++) {
            // Checking whether current
            // element is not equal to
            // it's previous element
            if (arr1[i] != arr1[i - 1]) {
                Console.Write(arr1[i] + " ");
                ++newtable[arr1[i]];
            }
        }
 
        // Finding only non common
        // elements from 2nd array
        for (int j = 0; j < arr2.Length; j++) {
            // By checking whether it's already
            // present in newtable or not
            if (newtable[arr2[j]] == 0) {
                Console.Write(arr2[j] + " ");
                ++newtable[arr2[j]];
            }
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr1 = { 1, 2, 2, 2, 3 };
        int[] arr2 = { 2, 3, 4, 5 };
 
        UnionArray(arr1, arr2);
    }
}
 
// This code is contributed by anuj_67.

JavaScript

<script>
// javascript program to find union of two
// sorted arrays (Handling Duplicates)
 
    function UnionArray(arr1 , arr2) {
        // Taking max element present in either array
        var m = arr1[arr1.length - 1];
        var n = arr2[arr2.length - 1];
 
        var ans = 0;
 
        if (m > n) {
            ans = m;
        } else
            ans = n;
 
        // Finding elements from 1st array
        // (non duplicates only). Using
        // another array for storing union
        // elements of both arrays
        // Assuming max element present
        // in array is not more than 10^7
        var newtable = Array(ans+1).fill(0);
 
        // First element is always
        // present in final answer
        document.write(arr1[0] + " ");
 
        // Incrementing the First element's count
        // in it's corresponding index in newtable
        newtable[arr1[0]]+=1;
 
        // Starting traversing the first
        // array from 1st index till last
        for (var i = 1; i < arr1.length; i++) {
            // Checking whether current element
            // is not equal to it's previous element
            if (arr1[i] != arr1[i - 1]) {
                document.write(arr1[i] + " ");
                newtable[arr1[i]]+= 1;
            }
        }
 
        // Finding only non common
        // elements from 2nd array
        for (var j = 0; j < arr2.length; j++) {
            // By checking whether it's already
            // present in newtable or not
            if (newtable[arr2[j]] == 0) {
                document.write(arr2[j] + " ");
                ++newtable[arr2[j]];
            }
        }
    }
 
    // Driver Code
        var arr1 = [ 1, 2, 2, 2, 3 ];
        var arr2 = [ 2, 3, 4, 5 ];
 
        UnionArray(arr1, arr2);
 
// This code is contributed by gauravrajput1
</script>
Producción

1 2 3 4 5

Complejidad Temporal: O(l1 + l2) 
Espacio Auxiliar: O(n)

Gracias a Sanjay Kumar por sugerir esta solución.

Otro enfoque usando TreeSet en Java : la idea del enfoque es construir un TreeSet e insertar todos los elementos de ambas arrays en él. Como un conjunto de árboles almacena solo valores únicos, solo conservará todos los valores únicos de ambas arrays.

A continuación se muestra la implementación del enfoque.

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to return the union of two arrays
    public static ArrayList<Integer>
    Unionarray(int arr1[], int arr2[],
               int n, int m)
    {
        TreeSet<Integer> set = new TreeSet<>();
         
        // Remove the duplicates from arr1[]
        for (int i : arr1)
            set.add(i);
       
        // Remove duplicates from arr2[]
        for (int i : arr2)
            set.add(i);
       
        // Loading set to array list
        ArrayList<Integer> list
            = new ArrayList<>();
        for (int i : set)
            list.add(i);
 
        return list;
    }
   
    // Driver code
    public static void main(String[] args)
    {
        int arr1[] = { 1, 2, 2, 2, 3 };
        int arr2[] = { 2, 3, 3, 4, 5, 5 };
        int n = arr1.length;
        int m = arr2.length;
       
        // Function call
        ArrayList<Integer> uni
            = Unionarray(arr1, arr2, n, m);
        for (int i : uni) {
            System.out.print(i + " ");
        }
    }
}
 
//  Contributed by ARAVA SAI TEJA
Producción

1 2 3 4 5

Complejidad de tiempo: O(m + n) donde ‘m’ y ‘n’ son el tamaño de las arrays
Espacio auxiliar: O(m*log(m)+n*log(n)) porque agregar un elemento a TreeSet requiere O( logn) tiempo que tomará agregar n elementos (nlogn)

Gracias a Arava Sai Teja por sugerir esta solución.

Otro enfoque que usa HashMap en Java: la idea del enfoque es construir un HashMap e insertar todos los elementos. Como HashMap tiene la complejidad de O(1) para inserción y búsqueda.

A continuación se muestra la implementación del enfoque.

Java

// Java code to implement the approach
import java.io.*;
import java.util.*;
import java.util.HashMap;
  
class GFG {
  
    // Function to return the union of two arrays
    public static ArrayList<Integer>
    Unionarray(int arr1[], int arr2[],
               int n, int m)
    {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
          
        // Remove the duplicates from arr1[]
        for (int i =0;i<arr1.length;i++)
        {
            if(map.containsKey(arr1[i]))
            {
                map.put(arr1[i], map.get(arr1[i]) + 1);
            }
            else
            {
                map.put(arr1[i], 1);
            }
        }
        
        // Remove duplicates from arr2[]
        for (int i =0;i<arr2.length;i++)
        {
            if(map.containsKey(arr2[i]))
            {
                map.put(arr2[i], map.get(arr2[i]) + 1);
            }
            else
            {
                map.put(arr2[i], 1);
            }
        }
        
        // Loading set to array list
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : map.keySet())
        {
            list.add(i);;
        }
  
        return list;
    }
    
    // Driver code
    public static void main(String[] args)
    {
        int arr1[] = { 1, 2, 2, 2, 3 };
        int arr2[] = { 2, 3, 3, 4, 5, 5 };
        int n = arr1.length;
        int m = arr2.length;
           System.out.println("Union is :");
        // Function call
        ArrayList<Integer> uni
            = Unionarray(arr1, arr2, n, m);
        for (int i : uni) {
            System.out.print(i + " ");
        }
    }
}
  
// This code is contributed by Aarti_Rathi
Producción

Union is :
1 2 3 4 5

Complejidad de tiempo: O(m + n) donde ‘m’ y ‘n’ son el tamaño de las arrays
Espacio auxiliar: O(m + n)

Gracias a Aarti Rathi por sugerir esta solución.

Otro enfoque optimizado : en el código anterior, usamos algo de espacio auxiliar adicional al crear newtable[]. Podemos reducir el programa de complejidad espacial para probar la función anterior a constante al verificar los elementos adyacentes al incrementar i o j de tal manera que i o j se muevan directamente al siguiente elemento distinto. Podemos realizar esta operación en el lugar (es decir, sin utilizar ningún espacio adicional).

C++

// This implementation uses vectors but can be easily modified to adapt arrays
#include <bits/stdc++.h>
using namespace std;
 
/* Helper function for printUnion().
   This same function can also be implemented as a lambda function inside printUnion().
*/
void next_distinct(const vector<int> &arr, int &x) // Moving to next distinct element
{
  // vector CAN be passed by reference to avoid unnecessary copies.
  // x(index) MUST be passed by reference so to reflect the change in the original index parameter
   
  /* Checks whether the previous element is equal to the current element,
       if true move to the element at the next index else return with the current index
  */
    do
    {
        ++x;
    } while (x < arr.size() && arr[x - 1] == arr[x]);
}
 
void printUnion(vector<int> arr1, vector<int> arr2)
{
    int i = 0, j = 0;
    while (i < arr1.size() && j < arr2.size())
    {
        if (arr1[i] < arr2[j])
        {
            cout << arr1[i] << " ";
            next_distinct(arr1, i); // Incrementing i to next distinct element
        }
        else if (arr1[i] > arr2[j])
        {
            cout << arr2[j] << " ";
            next_distinct(arr2, j); // Incrementing j to next distinct element
        }
        else
        {
            cout << arr1[i] << " ";
            // OR cout << arr2[j] << " ";
            next_distinct(arr1, i); // Incrementing i to next distinct element
            next_distinct(arr2, j); // Incrementing j to next distinct element
        }
    }
    // Remaining elements of the larger array
    while (i < arr1.size())
    {
        cout << arr1[i] << " ";
        next_distinct(arr1, i); // Incrementing i to next distinct element
    }
    while (j < arr2.size())
    {
        cout << arr2[j] << " ";
        next_distinct(arr2, j); // Incrementing j to next distinct element
    }
}
 
int main()
{
    vector<int> arr1 = {1, 2, 2, 2, 3};    // Duplicates Present
    vector<int> arr2 = {2, 3, 3, 4, 5, 5}; // Duplicates Present
 
    printUnion(arr1, arr2);
 
    return 0;
}
// This code is contributed by ciphersaini.
Producción

1 2 3 4 5

Complejidad de tiempo: O(m+n)   donde m & n son los tamaños de las arrays.
Espacio Auxiliar: O(1)

Intersección de arrays arr1[] y arr2[]

Para encontrar la intersección de 2 arrays ordenadas, siga el siguiente enfoque: 

1) Use dos variables de índice i y j, valores iniciales i = 0, j = 0 
2) Si arr1[i] es más pequeño que arr2[j] entonces incremente i. 
3) Si arr1[i] es mayor que arr2[j] entonces incremente j. 
4) Si ambos son iguales, imprima cualquiera de ellos e incremente tanto i como j.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find intersection of
// two sorted arrays
#include <bits/stdc++.h>
using namespace std;
 
/* Function prints Intersection of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
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 /* if arr1[i] == arr2[j] */
        {
            cout << arr2[j] << " ";
            i++;
            j++;
        }
    }
}
 
/* Driver program to test above function */
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]);
 
    // Function calling
    printIntersection(arr1, arr2, m, n);
 
    return 0;
}

C

// C program to find intersection of
// two sorted arrays
#include <stdio.h>
 
/* Function prints Intersection of arr1[] and arr2[]
   m is the number of elements in arr1[]
   n is the number of elements in arr2[] */
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 /* if arr1[i] == arr2[j] */
        {
            printf(" %d ", arr2[j++]);
            i++;
        }
    }
}
 
/* Driver program to test above function */
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

// Java program to find intersection of
// two sorted arrays
 
class FindIntersection {
    /* Function prints Intersection of arr1[] and arr2[]
       m is the number of elements in arr1[]
       n is the number of elements in 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);
    }
}

Python3

# Python program to find intersection of
# two sorted arrays
# Function prints Intersection of arr1[] and arr2[]
# m is the number of elements in arr1[]
# n is the number of elements in 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],end=" ")
            j += 1
            i += 1
 
# Driver program to test above function
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
m = len(arr1)
n = len(arr2)
printIntersection(arr1, arr2, m, n)
 
# This code is contributed by Pratik Chhajer

C#

// C# program to find Intersection of
// two sorted arrays
 
using System;
 
class GFG {
 
    /* Function prints Intersection of arr1[]
    and arr2[] m is the number of elements in arr1[]
    n is the number of elements in 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++;
            }
        }
    }
 
    // driver code
    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);
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP program to find intersection of
// two sorted arrays
 
/* Function prints Intersection
   of arr1[] and arr2[] m is the
   number of elements in arr1[]
   n is the number of elements
   in 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++;
             
        /* if arr1[i] == arr2[j] */
        else
        {
            echo $arr2[$j], " ";
            $i++;
            $j++;
        }
    }
}
 
// Driver Code
$arr1 = array(1, 2, 4, 5, 6);
$arr2 = array(2, 3, 5, 7);
 
$m = count($arr1);
$n = count($arr2);
 
// Function calling
printIntersection($arr1, $arr2, $m, $n);
 
// This code is contributed by anuj_67.
?>

JavaScript

<script>
 
// JavaScript program to find intersection of
// two sorted arrays
 
// Function prints Intersection of arr1[] and arr2[]
// m is the number of elements in arr1[]
// n is the number of elements in arr2[]
function printIntersection(arr1, arr2, m, n)
{
    var i = 0, j = 0;
    while (i < m && j < n)
    {
        if (arr1[i] < arr2[j])
            i++;
        else if (arr2[j] < arr1[i])
            j++;
        else
        {
            document.write(arr2[j++] + " ");
            i++;
        }
    }
}
 
// Driver code
var arr1 = [ 1, 2, 4, 5, 6 ];
var arr2 = [ 2, 3, 5, 7 ];
 
var m = arr1.length;
var n = arr2.length;
 
printIntersection(arr1, arr2, m, n);
 
// This code is contributed by shivanisinghss2110
 
</script>
Producción

2 5

Complejidad temporal: O(m + n)
Espacio auxiliar: O(1)

Manejo de duplicados en arrays: 
el código anterior no maneja elementos duplicados en arrays. La intersección no debe contar elementos duplicados. Para manejar duplicados, simplemente verifique si el elemento actual ya está presente en la lista de intersección. A continuación se muestra la implementación de este enfoque.

C++

// C++ program to find intersection of two sorted arrays
#include <bits/stdc++.h>
using namespace std;
 
/* Function prints Intersection of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
void print_intersection(int arr1[], int arr2[], int m, int n)
{
    int i = 0, j = 0;
    set<int> s;  //set for handling duplicate elements in intersection list
    while (i < m && j < n) {
        if (arr1[i] < arr2[j])
            i++;
        else if (arr2[j] < arr1[i])
            j++;
        else /* if arr1[i] == arr2[j] */
        {
            s.insert(arr2[j]);   //insertion in set s
            i++;
            j++;
        }
    }
    for(auto itr: s)  //printing intersection set list
    {
        cout<<itr<<" ";
        }
         
}
 
/* Driver code */
int main()
{
    int arr1[] = { 1, 2, 2, 3, 4 };
    int arr2[] = { 2, 2, 4, 6, 7, 8 };
 
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
 
    // Function calling
    print_intersection(arr1, arr2, m, n);
 
    return 0;
}
// This code is contributed by Goldentiger.

Java

// Java program to find intersection of two sorted arrays
import java.io.*;
import java.util.*;
class Print_Intersection {
    /* Function prints Intersection of arr1[] and arr2[]
    m is the number of elements in arr1[]
    n is the number of elements in arr2[] */
    static void print_intersection(int arr1[], int arr2[],
                                   int m, int n)
    {
        // set for handling duplicate elements in
        // intersection list
        Set<Integer> s = new TreeSet<Integer>();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (arr1[i] < arr2[j])
                i++;
            else if (arr2[j] < arr1[i])
                j++;
            else {
 
                s.add(arr2[j++]); // insertion in set s
                i++;
            }
        }
        for (int element :
             s) // printing intersection set list
        {
 
            System.out.print(element + " ");
        }
        System.out.println("");
    }
 
    public static void main(String args[])
    {
        int arr1[] = { 1, 2, 2, 3, 4 };
        int arr2[] = { 2, 2, 4, 6, 7, 8 };
        int m = arr1.length;
        int n = arr2.length;
        print_intersection(arr1, arr2, m, n);
    }
}
// This code is contributed by CipherBhandari

Python3

# Python3 program to find Intersection of two
# Sorted Arrays (Handling Duplicates)
def IntersectionArray(a, b, n, m):
    '''
    :param a: given sorted array a
    :param n: size of sorted array a
    :param b: given sorted array b
    :param m: size of sorted array b
    :return: array of intersection of two array or -1
    '''
 
    Intersection = []
    i = j = 0
     
    while i < n and j < m:
        if a[i] == b[j]:
 
            # If duplicate already present in Intersection list
            if len(Intersection) > 0 and Intersection[-1] == a[i]:
                i+= 1
                j+= 1
 
            # If no duplicate is present in Intersection list
            else:
                Intersection.append(a[i])
                i+= 1
                j+= 1
        elif a[i] < b[j]:
            i+= 1
        else:
            j+= 1
             
    if not len(Intersection):
        return [-1]
    return Intersection
 
# Driver Code
if __name__ == "__main__":
 
    arr1 = [1, 2, 2, 3, 4]
    arr2 = [2, 2, 4, 6, 7, 8]
     
    l = IntersectionArray(arr1, arr2, len(arr1), len(arr2))
    print(*l)
 
# This code is contributed by Abhishek Kumar

C#

// C# program to find Intersection of
// two sorted arrays
  
using System;
using System.Collections.Generic;
  
class GFG {
  
    /* Function prints Intersection of arr1[] and arr2[]
    m is the number of elements in arr1[]
    n is the number of elements in arr2[] */
    static void print_intersection(int []arr1, int []arr2, int m, int n)
    {
        int i = 0, j = 0;
        HashSet<int> s = new HashSet<int>();  //set for handling duplicate elements in intersection list
        while (i < m && j < n) {
            if (arr1[i] < arr2[j])
                i++;
            else if (arr2[j] < arr1[i])
                j++;
            else /* if arr1[i] == arr2[j] */
            {
                s.Add(arr2[j]);   //insertion in set s
                i++;
                j++;
            }
        }
        foreach(int k in s)  //printing intersection set list
        {
            Console.Write(k + " ");
        }
              
    }
  
    // driver code
    public static void Main()
    {
        int[] arr1 = { 1, 2, 2, 3, 4 };
        int[] arr2 = { 2, 2, 4, 6, 7, 8};
        int m = arr1.Length;
        int n = arr2.Length;
  
        print_intersection(arr1, arr2, m, n);
  
    }
}
  
// This code is contributed by Aarti_Rathi

JavaScript

<script>
 
// Python3 program to find Intersection of two
// Sorted Arrays (Handling Duplicates)
function IntersectionArray(a, b, n, m){
    // :param a: given sorted array a
    // :param n: size of sorted array a
    // :param b: given sorted array b
    // :param m: size of sorted array b
    // :return: array of intersection of two array or -1
 
    Intersection = []
    let i = j = 0
     
    while(i < n && j < m){
        if(a[i] == b[j]){
 
            // If duplicate already present in Intersection list
            if(Intersection.length > 0 && Intersection[Intersection.length-1] == a[i]){
                i+= 1
                j+= 1
            }
 
            // If no duplicate is present in Intersection list
            else{
                Intersection.push(a[i])
                i+= 1
                j+= 1
            }
        }
        else if(a[i] < b[j])
            i+= 1
        else
            j+= 1
    }
 
    if(!Intersection.length)
        return [-1]
    return Intersection
 
}
 
// Driver Code
 
let arr1 = [1, 2, 2, 3, 4]
let arr2 = [2, 2, 4, 6, 7, 8]
 
let l = IntersectionArray(arr1, arr2, arr1.length, arr2.length)
document.write(l)
 
// This code is contributed by shinjanpatra
 
 
</script>
Producción

2 4

Complejidad de Tiempo : O(m + n) 
Espacio Auxiliar : O(min(m, n))

Otro enfoque utilizando Tree Set: La idea de este enfoque es construir un conjunto de árboles para almacenar los elementos únicos de arri[]. Luego compare los elementos arr2[] con el conjunto de árboles y también verifique si eso se considera en la intersección para evitar duplicados.

A continuación se muestra la implementación del enfoque.

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the intersection
    // of two arrays
    public static ArrayList<Integer>
    Intersection(int arr1[], int arr2[],
                 int n, int m)
    {
        TreeSet<Integer> set = new TreeSet<>();
        // Removing duplicates from first array
        for (int i : arr1)
            set.add(i);
 
        ArrayList<Integer> list
            = new ArrayList<>();
         
        // Avoiding duplicates and
        // adding intersections
        for (int i : arr2)
            if (set.contains(i)
                && !list.contains(i))
                list.add(i);
         
        // Sorting
        Collections.sort(list);
        return list;
    }
   
    // Driver code
    public static void main(String[] args)
    {
        int arr1[] = { 1, 2, 4, 5, 6 };
        int arr2[] = { 2, 3, 5, 7 };
        int n = arr1.length;
        int m = arr2.length;
         
        // Function call
        ArrayList<Integer> inter
            = Intersection(arr1, arr2, n, m);
        for (int i : inter) {
            System.out.print(i + " ");
        }
    }
}
 
//  Contributed by ARAVA SAI TEJA
Producción

2 5

Tiempo Complejidad: O(m+n)
Espacio Auxiliar: O(m+n)

Gracias a Arava Sai Teja por sugerir esta solución. 

Otro enfoque que es útil cuando la diferencia entre los tamaños de dos arrays dadas es significativa.  
La idea es iterar a través de la array más corta y hacer una búsqueda binaria para cada elemento de la array corta en la array grande (tenga en cuenta que las arrays están ordenadas). La complejidad temporal de esta solución es O(min(mLogn, nLogm)). Esta solución funciona mejor que el enfoque anterior cuando la relación entre longitudes más grandes y más pequeñas es mayor que el orden logarítmico.

Consulte la siguiente publicación para arrays sin clasificar. 
Encuentre la unión y la intersección de dos arrays no ordenadas
Escriba comentarios si encuentra algún error en los códigos/algoritmos anteriores, o encuentre otras formas de resolver el mismo problema. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *