Maison >développement back-end >C++ >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.
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.
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.
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
#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 ); }
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,
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++.
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
#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 ); }
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,
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!