Programme C++ pour trouver des éléments communs à deux tableaux

Utilisez des tableaux et des structures de données pour stocker des données homogènes (identiques) sur plusieurs emplacements mémoire. Le principal avantage de l’utilisation de tableaux est que nous pouvons y accéder de n’importe où en utilisant les paramètres d’index. Le fait que les données doivent être ajoutées et supprimées séquentiellement transforme cette structure de données en une structure linéaire. Pour récupérer un élément d’un tableau, il suffit d’utiliser le numéro d’index ou de position entre crochets. Dans cet article, nous utiliserons C++ pour obtenir les seuls éléments communs présents dans deux tableaux.

Comprendre les concepts et illustrer avec des exemples

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]

Dans le premier tableau, il y a neuf éléments et dans le deuxième tableau, il y a huit éléments. Les deux tableaux peuvent donc ne pas avoir la même taille. Notre tâche est de trouver les éléments communs entre ces deux tableaux. Nous verrons ici quelques astuces pour résoudre ce problème.

Solution naïve

La première et la plus courante solution consiste à parcourir chaque élément du premier tableau et à rechercher dans le deuxième tableau chaque entrée du premier tableau. Cette solution est moins efficace, mais plus simple. Jetons un coup d'œil à l'algorithme et à l'implémentation correspondante.

Algorithme

• Prenez deux tableaux A et B en entrée

• Définissez un autre tableau D pour contenir tous les éléments répétés

• Pour chaque élément e1 dans A, procédez comme suit

  • Pour chaque élément e2 dans B, procédez comme suit

    • Si e1 = e2, alors

      • Insérez e1 dans D

    • Fin si

  • Fin du cycle

• Fin du cycle

• Retour à D

La traduction chinoise de

Exemple

est :

Exemple

#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 ); 
}

Sortie

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,

Utilisez des vecteurs et la fonction set_intersection()

En utilisant C++ STL, la fonction set_intersection() renvoie les éléments communs en tant qu'objet itérateur. Mais pour utiliser cette fonction, nous devons trier le tableau par ordre croissant. Jetons un coup d'œil à l'algorithme et au code d'implémentation C++.

Algorithme

• Prenez deux tableaux A et B en entrée

• Définissez un autre tableau D pour contenir tous les éléments répétés

• Créez un itérateur pour un tableau d'éléments répétés

• Utilisez la méthode set_intersection() pour effectuer l'opération d'intersection sur les tableaux A et B et stocker le résultat dans le tableau D

• Retour à D

La traduction chinoise de

Exemple

est :

Exemple

#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 ); 
}

Sortie

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,

Conclusion

Dans cet article, nous avons vu deux façons de trouver des éléments communs à partir d'une collection d'éléments ou de deux tableaux. La première solution naïve consiste à utiliser deux tableaux statiques et à trouver les éléments communs en analysant chaque élément un par un. La complexité temporelle de cette solution est O(n.m), où n est la taille du premier tableau et m est la taille du deuxième tableau. La méthode suivante utilise la méthode set_intersection() basée sur C++ STL. Dans cette méthode, nous devons utiliser des vecteurs triés. La méthode renvoie ensuite un objet itérateur d'élément public. Nous pouvons en créer un vecteur et le renvoyer.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!