C++ program to find common elements from two arrays

Use arrays and data structures to store homogeneous (identical) data in multiple memory locations. The main advantage of using arrays is that we can access them from anywhere by using index parameters. The fact that data must be added and removed sequentially turns this data structure into a linear structure. To retrieve an element from an array, we just need to use the index or position number inside square brackets. In this article, we will use C to get the only common elements present in two arrays.

Understand concepts and illustrate with examples

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]

In the first array, there are nine elements, and in the second array, there are eight elements. So the two arrays may not be the same size. Our task is to find the common elements between these two arrays. Here we will see some tips to solve this problem.

Naive solution

The first and most common solution is to loop through each element of the first array and search in the second array for each entry of the first array. This solution is less efficient, but simpler. Let's take a look at the algorithm and corresponding implementation.

algorithm

• Take two arrays A and B as input

• Define another array D to hold all repeated elements

• For each element e1 in A, perform the following operations

  • For each element e2 in B, perform the following operations

    • If e1 = e2, then

      • Insert e1 into D

    • End if

  • End loop

• End loop

• Return D

The Chinese translation of

Example

is:

Example

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

Output

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,

Use vectors and set_intersection() function

Using the C STL, the set_intersection() function returns the common elements as an iterator object. But to use this function we have to sort the array in ascending order. Let's take a look at the algorithm and C implementation code.

algorithm

• Take two arrays A and B as input

• Define another array D to hold all repeated elements

• Create an iterator for an array of repeated elements

• Use the set_intersection() method to perform the intersection operation on the A and B arrays and store the result in the D array

• Return D

The Chinese translation of

Example

is:

Example

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

Output

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,

in conclusion

In this article, we have seen two ways to find common elements from a collection of elements or two arrays. The first naive solution is to use two static arrays and find the common elements by scanning each element one by one. The time complexity of this solution is O(n.m), where n is the size of the first array and m is the size of the second array. The next method uses the C STL-based set_intersection() method. In this method we need to use sorted vectors. The method then returns a public element iterator object. We can create a vector from it and return it.

The above is the detailed content of C++ program to find common elements from two arrays. For more information, please follow other related articles on the PHP Chinese website!