c++arraysalgorithm

How to get intersection of two Arrays


I have two integer arrays

    int A[] = {2, 4, 3, 5, 6, 7};
    int B[] = {9, 2, 7, 6};

And i have to get intersection of these array.

i.e. output will be - 2,6,7

I am thinking to sove it by saving array A in a data strcture and then i want to compare all the element till size A or B and then i will get intersection.

Now i have a problem i need to first store the element of Array A in a container.

shall i follow like -

int size = sizeof(A)/sizeof(int);

To get the size but by doing this i will get size after that i want to access all the elemts too and store in a container.

Here i the code which i am using to find Intersection ->

#include"iostream"

using namespace std;


int A[] = {2, 4, 3, 5, 6, 7};
int B[] = {9, 2, 7, 6};

int main()
{
    int sizeA = sizeof(A)/sizeof(int);

    int sizeB = sizeof(B)/sizeof(int);

    int big =  (sizeA > sizeB) ? sizeA : sizeB;

    int small =  (sizeA > sizeB) ? sizeB : sizeA;

    for (int i = 0; i <big ;++i)
    {
        for (int j = 0; j <small ; ++j)
        {
            if(A[i] == B[j])
            {
                cout<<"Element is -->"<<A[i]<<endl;
            }
        }
    }

    return 0;
}

Solution

  • Just use a hash table:

    #include <unordered_set>  // needs C++11 or TR1 
    // ...
    unordered_set<int> setOfA(A, A + sizeA);
    

    Then you can just check for every element in B, whether it's also in A:

    for (int i = 0; i < sizeB; ++i) {
        if (setOfA.find(B[i]) != setOfA.end()) {
            cout << B[i] << endl;
        }
    }
    

    Runtime is expected O(sizeA + sizeB).