Programm zum Finden von Vereinigung und Schnittmenge zweier sortierter Arrays

Programm zum Finden von Vereinigung und Schnittmenge zweier sortierter Arrays
  • Schreiben Sie ein Programm, um Vereinigung und Schnittmenge von zwei sortierten Integer-Arrays zu finden.
  • Algorithmus zum Finden von Vereinigung und Schnittmenge von zwei sortierten Arrays.

Bei zwei sortierten Integer-Arrays müssen wir die Vereinigung und den Schnittpunkt zweier gegebener Arrays finden. Zwei sortierte Arrays seien
Array1 =[1 3 5 6 8 10 11 14 15 20]
Array2 =[2 3 5 7 9 10]

  • UNION :Die Vereinigung zweier Arrays ist ein Array, das alle Elemente enthält, die in mindestens einem der beiden Arrays enthalten sind. Wenn ein Element in beiden Arrays vorhanden ist oder mehrmals vorhanden ist, wird es nur einmal in das Union-Array aufgenommen.
    • Die Vereinigung der oben genannten zwei gegebenen Arrays ist [1 2 3 5 6 7 8 9 10 11 14 15 20]
  • KREUZUNG :Schnittpunkt zweier Arrays ist ein Array, das alle Elemente enthält, die in beiden Arrays enthalten sind.
    • Schnittpunkt der oben genannten zwei gegebenen Arrays ist [3 5 10]

Seien Array1 und Array2 zwei sortierte Arrays der Größe M bzw. N.
Vereinigung zweier sortierter Arrays:O(M + N)
Algorithmus zum Finden der Vereinigung zweier sortierter Arrays
  • Zwei Variablen index1 und index2 auf 0 initialisieren (Index des kleinsten Elements beider Arrays)
  • if(array1[index1]
  • Else if(array2[index2]
  • Wenn beide gleich sind (array2[index2] ==array1[index1]), dann drucke ein beliebiges Element und erhöhe seinen Index.
  • Wenn ein Array vor einem anderen endet, dann drucke das verbleibende Element eines anderen Arrays.

C-Programm zum Finden der Vereinigung zweier sortierter Arrays

#include <stdio.h>
/*
NOTE : In this program , we are assuming unique elements in array 
*/

/* This function prints Union of two sorted array */
void printUnion(int *array1, int size1, int *array2, int size2) {
   int index1 = 0, index2 = 0;
   /* This loop will continue untill one 
   of the array traversal completes */
   while(index1 < size1 && index2 < size2) {
      if (array1[index1] < array2[index2])
         /*array1[index1]is smaller, print it and increment index1 */ 
         printf("%d ", array1[index1++]);
      else if (array2[index2] < array1[index1])
         /*array2[index2]is smaller, print it and increment index2 */ 
         printf("%d ", array2[index2++]);
      else {
         /* Both equal, print anyone and increment both indexes */
         printf("%d ", array2[index2]);
         index1++;
         index2++;
      }
  }
 
  /* Print remianing elements */
  while(index1 < size1)
    printf("%d ", array1[index1++]);
   
  while(index2 < size2)
    printf("%d ", array2[index2++]);
}

int main(){
    int array1[10] = {1, 3, 5, 6, 8, 10, 11, 14, 15, 20};
    int array2[6] = {2, 3, 5, 7, 9, 10}; 

    printUnion(array1, 10, array2, 6);

    return 0;
}
Ausgabe
1 2 3 5 6 7 8 9 10 11 14 15 20
Schnittpunkt zweier sortierter Arrays:O(M + N)
Algorithmus zum Finden der Vereinigung zweier sortierter Arrays
  • Initialisieren Sie zwei Variablen index1 und index2 auf 0 (Index des kleinsten Elements beider Arrays)
  • if(array1[index1]
  • Else if(array2[index2]
  • Wenn beide gleich sind (array2[index2] ==array1[index1]), dann drucke ein beliebiges Element und erhöhe seinen Index.
  • Wenn irgendein Array vor einem anderen endet, dann zurück.

C-Programm zum Finden der Schnittmenge zweier sortierter Arrays

#include <stdio.h>
/*
NOTE : In this program , we are assuming unique elements in array 
*/

/* This function prints Union of two sorted array */
void printIntersection(int *array1, int size1, int *array2, int size2) {
  int index1 = 0, index2 = 0;
  /* This loop will continue untill one 
  of the array traversal completes */
  while(index1 < size1 && index2 < size2) {
    if (array1[index1] < array2[index2])
    /*array1[index1]is smaller, increment index1 */ 
      index1++;
    else if (array2[index2] < array1[index1])
    /*array2[index2]is smaller, increment index2 */ 
      index2++;
    else {
    /* Both equal, print anyone and increment both indexes */
      printf("%d ", array2[index2]);
      index1++;
      index2++;
    }
  }
}

int main(){
    int array1[10] = {1, 3, 5, 6, 8, 10, 11, 14, 15, 20};
    int array2[6] = {2, 3, 5, 7, 9, 10}; 

    printIntersection(array1, 10, array2, 6);

    return 0;
}
Ausgabe
3 5 10