C++-Programm zum Finden gemeinsamer Elemente aus zwei Arrays

Verwenden Sie Arrays und Datenstrukturen, um homogene (identische) Daten an mehreren Speicherorten zu speichern. Der Hauptvorteil der Verwendung von Arrays besteht darin, dass wir mithilfe von Indexparametern von überall auf sie zugreifen können. Dadurch, dass Daten nacheinander hinzugefügt und entfernt werden müssen, wird diese Datenstruktur zu einer linearen Struktur. Um ein Element aus einem Array abzurufen, müssen wir lediglich den Index oder die Positionsnummer in eckigen Klammern verwenden. In diesem Artikel verwenden wir C++, um die einzigen gemeinsamen Elemente in zwei Arrays abzurufen.

Konzepte verstehen und anhand von Beispielen veranschaulichen

Given first array A = [10, 14, 65, 85, 96, 12, 35, 74, 69]
Given second array B = [23, 65, 89, 96, 12, 37, 71, 69]

The common elements in arrays A and B are [65, 96, 12, 69]

Im ersten Array gibt es neun Elemente und im zweiten Array gibt es acht Elemente. Daher sind die beiden Arrays möglicherweise nicht gleich groß. Unsere Aufgabe besteht darin, die gemeinsamen Elemente dieser beiden Arrays zu finden. Hier sehen wir einige Tipps zur Lösung dieses Problems.

Naive Lösung

Die erste und häufigste Lösung besteht darin, jedes Element des ersten Arrays zu durchlaufen und im zweiten Array nach jedem Eintrag des ersten Arrays zu suchen. Diese Lösung ist weniger effizient, aber einfacher. Werfen wir einen Blick auf den Algorithmus und die entsprechende Implementierung.

Algorithmus

• Nehmen Sie zwei Arrays A und B als Eingabe

• Definieren Sie ein weiteres Array D, um alle wiederholten Elemente aufzunehmen

• Führen Sie für jedes Element e1 in A Folgendes aus

  • Führen Sie für jedes Element e2 in B Folgendes aus

    • Wenn e1 = e2, dann

      • E1 in D einfügen

    • Ende wenn

  • Den Zyklus beenden

• Den Zyklus beenden

• Zurück nach D

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#include <iostream>
# define Z 50

using namespace std;

void displayArr(int arr[], int n){
   for( int i = 0; i < n; i++ ){
      cout << arr[ i ] << ", ";
   }
   cout << endl;
}

void findCommonElement( int A[], int n, int B[], int m, int D[], int &k ) {
   k = 0;
   for( int i = 0; i < n; i++ ) {
      for( int j = 0; j < m; j++ ) {
         if( A[ i ] == B[ j ] ) {
            D[ k ] = A[ i ];
            k = k + 1;
         }
      }
   }
}

int main() {
   int A[ Z ] = { 10, 14, 65, 85, 96, 12, 35, 74, 69 };
   int n = 9;
   
   int B[ Z ] = { 23, 65, 89, 96, 12, 37, 71, 69 };
   int m = 8;
   
   int D[ Z ];
   int k = 0;
   
   cout << "Given first array A: ";
   displayArr( A, n );
   
   cout << "Given second array B: ";
   displayArr( B, m );
   
   findCommonElement( A, n, B, m, D, k );
   cout << "The common elements are: ";
   displayArr( D, k ); 
}

Ausgabe

Given first array A: 10, 14, 65, 85, 96, 12, 35, 74, 69, 
Given second array B: 23, 65, 89, 96, 12, 37, 71, 69, 
The common elements are: 65, 96, 12, 69,

Verwenden Sie Vektoren und die Funktion set_intersection()

Mit C++ STL gibt die Funktion set_intersection() die gemeinsamen Elemente als Iteratorobjekt zurück. Um diese Funktion nutzen zu können, müssen wir das Array jedoch in aufsteigender Reihenfolge sortieren. Werfen wir einen Blick auf den Algorithmus und den C++-Implementierungscode.

Algorithmus

• Nehmen Sie zwei Arrays A und B als Eingabe

• Definieren Sie ein weiteres Array D, um alle wiederholten Elemente aufzunehmen

• Erstellen Sie einen Iterator für ein Array wiederholter Elemente

• Verwenden Sie die Methode set_intersection(), um die Schnittoperation für die Arrays A und B durchzuführen und das Ergebnis im Array D zu speichern

• Zurück nach D

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#include <iostream>
#include <algorithm>
#include <vector>
# define Z 50

using namespace std;

void displayArr( vector<int> v ){
   for( int i = 0; i < v.size() ; i++ ){
      cout << v[ i ] << ", ";
   }
   cout << endl;
}

vector<int> findCommonElement( vector<int> A, vector<int> B ) {
   sort( A.begin(), A.end() );
   sort( B.begin(), B.end() );
   vector<int> duplicates;
   
   vector<int> D( A.size() + B.size() );
   vector<int>::iterator Dit, st;
  
   Dit = set_intersection( A.begin(), A.end(), B.begin(), B.end(), D.begin() );
   
   for( st = D.begin(); st != Dit; ++st )
      duplicates.push_back( *st ) ;
   return duplicates;
}

int main() {
   vector<int> A = { 10, 14, 65, 85, 96, 12, 35, 74, 69 }; 
   vector<int> B = { 23, 65, 89, 96, 12, 37, 71, 69 }; 
   vector<int> D;
   
   cout << "Given first array A: ";
   displayArr( A );
   
   cout << "Given second array B: ";
   displayArr( B );
   
   D = findCommonElement( A, B );
   cout << "The common elements are: ";
   displayArr( D ); 
}

Ausgabe

Given first array A: 10, 14, 65, 85, 96, 12, 35, 74, 69, 
Given second array B: 23, 65, 89, 96, 12, 37, 71, 69, 
The common elements are: 12, 65, 69, 96,

Fazit

In diesem Artikel haben wir zwei Möglichkeiten gesehen, gemeinsame Elemente aus einer Sammlung von Elementen oder zwei Arrays zu finden. Die erste naive Lösung besteht darin, zwei statische Arrays zu verwenden und die gemeinsamen Elemente zu finden, indem jedes Element einzeln gescannt wird. Die zeitliche Komplexität dieser Lösung beträgt O(n.m), wobei n die Größe des ersten Arrays und m die Größe des zweiten Arrays ist. Die nächste Methode verwendet die C++ STL-basierte set_intersection()-Methode. Bei dieser Methode müssen wir sortierte Vektoren verwenden. Die Methode gibt dann ein öffentliches Element-Iteratorobjekt zurück. Wir können daraus einen Vektor erstellen und ihn zurückgeben.

Das obige ist der detaillierte Inhalt vonC++-Programm zum Finden gemeinsamer Elemente aus zwei Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!