Preventing duplicates from being stored when filling dynamic array with values from two different arrays

Question

I need to know a method to keep duplicate numbers from being stored in a new array when taking numbers from two different arrays. The function is supposed to store each 'unique' value once and not store duplicate values again.

Here is my function code so far:

int * arrayIntersect(int *sizeOfResult, const int *a, const int *b, int sizeOfA, int sizeOfB){
int i;
int j;
int k = 0;
int c[(sizeOfA + sizeOfB)];

    for(j = 0; j < sizeOfB; j++){
        for(i = 0; i < sizeOfA; i++){
            if(a[i] == b[j]){
                c[k] = a[i];
                (*sizeOfResult)++;
                k++;
            }   
        }
    }
int *d = (int *)malloc(sizeof(int) * *sizeOfResult);
    for(i = 0; i < *sizeOfResult; i++){
        d[i] = c[i];
    }
return d;

}

It prints the values I need, but I want to eliminate the same number from showing up multiple times when printing the contents of the new dynamic array.

Any idea on how to improve my code to allow prevent duplication?

Answer 1

The proper way to do it is having the arrays ordered and then doing a binary search for each insertion like @Murilo Vasoncelos pointed out.

Below is a quick and dirty solution that loops through a and b and for each iteration checks if the number has been inserted before. If it isn't, it inserts it.

int duplicate = 0;
*sizeOfResult = 0;
for(j = 0; j < sizeOfA; j++){
    for(i = 0; i < (*sizeOfResult); i++){
        if(c[i] == a[j]){
            duplicate = 1;
            break;
        }   
    }
    if (!duplicate)
    {
        c[(*sizeOfResult)] = a[i];
        (*sizeOfResult)++;
    }
    duplicate = 0;
}
for(j = 0; j < sizeOfB; j++){
    for(i = 0; i < (*sizeOfResult); i++){
        if(c[i] == b[j]){
            duplicate = 1;
            break;
        }   
    }
    if (!duplicate)
    {
        c[(*sizeOfResult)] = b[i];
        (*sizeOfResult)++;
    }
    duplicate = 0;
}

Answer 2

If your arrays a and b are ordered, you can simply use this linear algorithm for array intersection:

int* inter(int* szr, int* a, int* b, int sza, int szb)
{
    int c[MAX(sza, szb)];
    int i, j, k = 0;

    for (i = 0, j = 0; i < sza && j < szb;) {
        if (a[i] == b[j]) {
            if (k == 0 || c[k - 1] < a[i]) {
                c[k++] = a[i];
            }

            i++;
            j++;
        }
        else if (a[i] < b[j]) {
            i++;
        }
        else {
            j++;
        }
    }

    *szr = k;

    int* ans = (int*)malloc(sizeof(int) * k);
    for (i = 0; i < k; ++i) {
        ans[i] = c[i];
    }

    return ans;
}