#include <stdio.h> #include <stdlib.h> /* Puzzle C44 -- fill a third array with the elements | two other arrays have in common | | Write function that looks at two arrays and fills a | third array with the elements that are common to the | first two arrays. The third array has only one copy | of each element in common with the other two arrays. | The first two arrays may be of unequal sizes. | Return the number of elements in the third array. | */ int commonElements( int arrA[], int sizeA, int arrB[], int sizeB, int out[], int sizeOut ) { int eleA, eleB, eleC; int ixa, ixb, ixc; int countOut = 0; int foundB, foundOut; /* look sequentially at elements in arrA */ for ( ixa=0; ixa<sizeA; ixa++ ) { eleA = arrA[ixa]; /* check if eleA is also in arrB */ foundB = 0; for ( ixb=0; ixb<sizeB && !foundB; ixb++ ) { if ( eleA==arrB[ixb] ) foundB = 1; } /* add it to out if it is not already there */ if ( foundB ) { foundOut = 0; for ( ixc=0; ixc<countOut && !foundOut; ixc++ ) if ( eleA==out[ixc] ) foundOut = 1; if ( !foundOut && countOut < sizeOut ) { out[countOut] = eleA; countOut++ ; } } } return countOut ; } void printArray( int arr[], int size ) { const int N = 10; int j; for ( j=0; j<size; j++ ) { if ( j%N == N-1 ) printf("%4d\n", arr[j] ); else printf("%4d ", arr[j] ); } } int main(int argc, char *argv[]) { int count ; int arrA[] = { 3, 3, 5, 8, 8, 9, 7, 0, -1, -2, 1, 1 }; int arrB[] = { 3, 3, 3, 3, 3, 5, 5, 5, 5, 5 }; int sizeA = sizeof( arrA )/sizeof( int ); int sizeB = sizeof( arrB )/sizeof( int ); int arrC[sizeA+sizeB]; printf("Array A:\n"); printArray( arrA, sizeA ); printf("\nArray B:\n"); printArray( arrB, sizeB ); count = commonElements( arrA, sizeA, arrB, sizeB, arrC, sizeA+sizeB ); printf("\n\nElements in Common:\n"); printArray( arrC, count ); printf("\n\n"); system("PAUSE"); return 0; }
Comments: Say that both arrays are N elements long. Then the best case for this function is if the first array contains only N instances of the same value x, and this value is the first one in the second array. Then the first array is inspected in N iterations, and each iteration does a fixed amount of work with the other two arrays. So the best case is O(N).
The worst case (for both arrays N elements long) is if the arrays have no elements in common. Then each iteration over the first array requires a search through the the N elements of the second array, for O(N2) operations total.
Another case (for both arrays N elements long) is if the two arrays have N elements in common, so that the output array will grow to be N elements long. Now the N elements of the first array are inspected. For each of these elements, it takes (on the average) N/2 iterations through the second array to find the matching element, and (on the average) N/2 iterations through the output array to check for duplicates. So this also is a total of O(N2) operations.
The input arrays could be sorted first, at a cost of N·log N, each. A single pass through the sorted arrays can produce the output array, at a cost of N. The total cost for this approach is 2·N·log N + N, which is O( N·log N ).
If the arrays are expected to be more than 50 or so elements long, the sort-first approach should be used.