Compare 2 elements of two arrays in C++

Question

I have two arrays each array has some values for instance:

int a[] =  {1, 2, 3, 4};
int b[] =  {0, 1, 5, 6};

now I need to compare the elements of the array (a) with elements in array (b).. if is there any match the program should return an error or print "error there is a duplicate value" etc.. in the above situation, it should return an error coz a[0] = b[1] because both are have same values.

how can I do this??

thanks.

Answer 1

If the arrays are this small, I would just do a brute force approach, and loop through both arrays:

for (int i=0;i<4;++i)
{
    for (int j=0;j<4;++j)
    {
        if (a[i] == b[j])
        {
            // Return an error, or print "error there is a duplicate value" etc
        }
    }
}

If you're going to be dealing with large arrays, you may want to consider a better algorithm, however, as this is O(n^2).

If, for example, one of your arrays is sorted, you could check for matches much more quickly, especially as the length of the array(s) gets larger. I wouldn't bother with anything more elaborate, though, if your arrays are always going to always be a few elements in length.

Answer 2

Assuming both arrays are sorted, you can step them though them like this:

// int array1[FIRSTSIZE];
// int array2[SECONDSIZE];
for(int i=0, j=0; i < FIRSTSIZE && j < SECONDSIZE; ){
    if(array1[i] == array2[j]){
        cout << "DUPLICATE AT POSITION " << i << "," << j << endl;
        i++;
        j++;
    }
    else if(array1[i] < array2[j]){
        i++;
    }
    else{
        j++;
    }
}

This should have linear complexity, but it only works if they're sorted.

Answer 3

The solution for sorted arrays has already been posted. If the arrays are not sorted, you can build a set (e.g. std::set or a hash set) out of each and see if the sets are disjoint. You probably have to store value–index pairs in the sets to find out which index was duplicate (and overload the comparison operators appropriately). This might give O(n log n) complexity.