Problem
Given two array of integers write two functions that will return an Union and Intersection.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Compute Union and Intersection
Created Date : 15-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
using namespace std;
int Compare( const void *arg1, const void *arg2 )
{
if (*(int*)arg1 < *(int *)arg2){
return -1;
}
else if (*(int*)arg1 == *(int *)arg2){
return 0;
}
else{
return 1;
}
}
void PrintArray(int* arr, int len)
{
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
}
void UnionAndIntersection(int* arr1, int len1,
int* arr2, int len2,
int* un, int& unLen,
int* intersec, int& inLen)
{
qsort(arr1, len1, sizeof(arr1[0]), Compare);
cout << "The array 1 after sorting is : " << endl;
PrintArray(arr1, len1);
qsort(arr2, len2, sizeof(arr1[0]), Compare);
cout << "The array 2 after sorting is : " << endl;
PrintArray(arr2, len2);
int *pArr1(arr1), *pArr2(arr2), *pUnion(un), *pIntersection(intersec);
while(pArr1 < arr1 + len1 && pArr2 < arr2 + len2){
if(*pArr1 == *pArr2){
*pUnion ++ = *pArr1 ++;
*pIntersection ++ = *pArr2 ++;
}
else if(*pArr1 < *pArr2){
*pUnion ++ = *pArr1 ++;
}
else{
*pUnion ++ = *pArr2 ++;
}
while(pArr1 < arr1 + len1 && *pArr1 == *(pArr1 - 1)){ pArr1 ++;}
while(pArr2 < arr2 + len2 && *pArr2 == *(pArr2 - 1)){ pArr2 ++;}
}
while(pArr1 < arr1 + len1){
*pUnion ++ = *pArr1 ++;
while(pArr1 < arr1 + len1 && *pArr1 == *(pArr1 - 1)){ pArr1 ++;}
}
while(pArr2 < arr2 + len2){
*pUnion ++ = *pArr2 ++;
while(pArr2 < arr2 + len2 && *pArr2 == *(pArr2 - 1)){ pArr2 ++;}
}
unLen = pUnion - un;
inLen = pIntersection - intersec;
}
int main(int argc, char* argv[])
{
int *arr1, *arr2;
int len1, len2;
int *un, *intersec;
for(int i = 0; i < 10; ++i){
len1 = rand() % 10 + 1;
len2 = rand() % 10 + 1;
arr1 = new int[len1];
arr2 = new int[len2];
intersec = new int[(len1 < len2) ? len1 : len2];
un = new int[len1 + len2];
int unLen(0), inLen(0);
for(int j = 0; j < len1; j++){
arr1[j] = rand() % 5;
}
for(int j = 0; j < len2; j++){
arr2[j] = rand() % 5;
}
cout << "The array 1 is : " << endl;
PrintArray(arr1, len1);
cout << "The array 2 is : " << endl;
PrintArray(arr2, len2);
UnionAndIntersection(arr1, len1, arr2, len2,
un, unLen, intersec, inLen);
cout << "The union of two arrays is :" << endl;
PrintArray(un, unLen);
cout << "The intersection of two array is: " << endl;
PrintArray(intersec, inLen);
cout << "------------------------------------------" << endl;
delete[] un;
delete[] intersec;
delete[] arr1;
delete[] arr2;
}
return 0;
}
Output
The array 1 is :
4 0
The array 2 is :
4 4 3 3 2 4 0 0
The array 1 after sorting is :
0 4
The array 2 after sorting is :
0 0 2 3 3 4 4 4
The union of two arrays is :
0 2 3 4
The intersection of two array is:
0 4
------------------------------------------
The array 1 is :
1 1
The array 2 is :
0 2 2 1 1 4 2 3
The array 1 after sorting is :
1 1
The array 2 after sorting is :
0 1 1 2 2 2 3 4
The union of two arrays is :
0 1 2 3 4
The intersection of two array is:
1
------------------------------------------
The array 1 is :
1 1 3
The array 2 is :
0 2 1
The array 1 after sorting is :
1 1 3
The array 2 after sorting is :
0 1 2
The union of two arrays is :
0 1 2 3
The intersection of two array is:
1
------------------------------------------
The array 1 is :
4 2
The array 2 is :
2 4 0 4 3 1 2 3 3
The array 1 after sorting is :
2 4
The array 2 after sorting is :
0 1 2 2 3 3 3 4 4
The union of two arrays is :
0 1 2 3 4
The intersection of two array is:
2 4
------------------------------------------
The array 1 is :
1 3 3 2 4
The array 2 is :
2 2
The array 1 after sorting is :
1 2 3 3 4
The array 2 after sorting is :
2 2
The union of two arrays is :
1 2 3 4
The intersection of two array is:
2
------------------------------------------
The array 1 is :
3 1 4 3 1 0 0 2
The array 2 is :
3 1 0 2 4 3 1 0 0 4
The array 1 after sorting is :
0 0 1 1 2 3 3 4
The array 2 after sorting is :
0 0 0 1 1 2 3 3 4 4
The union of two arrays is :
0 1 2 3 4
The intersection of two array is:
0 1 2 3 4
------------------------------------------
The array 1 is :
1
The array 2 is :
1
The array 1 after sorting is :
1
The array 2 after sorting is :
1
The union of two arrays is :
1
The intersection of two array is:
1
------------------------------------------
The array 1 is :
4 3 4 4
The array 2 is :
1 0 1 1 1 3 4 4 1
The array 1 after sorting is :
3 4 4 4
The array 2 after sorting is :
0 1 1 1 1 1 3 4 4
The union of two arrays is :
0 1 3 4
The intersection of two array is:
3 4
------------------------------------------
The array 1 is :
3 3 2 4
The array 2 is :
1 3 0 4 3 4 0 2
The array 1 after sorting is :
2 3 3 4
The array 2 after sorting is :
0 0 1 2 3 3 4 4
The union of two arrays is :
0 1 2 3 4
The intersection of two array is:
2 3 4
------------------------------------------
The array 1 is :
1 1 0 4 2 0 4
The array 2 is :
2 3 2 2
The array 1 after sorting is :
0 0 1 1 2 4 4
The array 2 after sorting is :
2 2 2 3
The union of two arrays is :
0 1 2 3 4
The intersection of two array is:
2
------------------------------------------
Press any key to continue . . .