一、数组内数据无序且可以重复
本文采用一种交换的方式来求出两个数组的并集，交集和差集，这种算法运算速度较快，内存消耗空间较少，是一个值得学习的好方法，另外，作者提醒您，重要的不是算法本身，而是该算法会开拓我们的思维空间，要注意对问题的多思考。
算法概述：
两个任意元素的数组，比较出两个数组中相同的元素和不同的元素。
元素划分：
计算过程中，两个数组内部元素的划分：
算法流程：
从数组1的尚未比较的元素中拿出第一个元素array1(i)，用array1(i)与array2(j)进行比较（其中j>i且j<array2的长度），可能出现下面两种情况，
1．
2．
算法实现代码：
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void main()
{
//定义两个数组
int array1[] = {7,1,2,5,4,3,5,6,3,4,5,6,7,3,2,5,6,6};
int size1 = sizeof(array1) / sizeof(array1[0]);
int array2[] = {8,2,1,3,4,5,3,2,4,5,3,2,1,3,5,4,6,9};
int size2 = sizeof(array2) / sizeof(array2[0]);;
int end = size1;
bool swap = false;//标识变量，表示两种情况中的哪一种
for(int i=0 ; i < end;)
{
swap = false;//开始假设是第一种情况
for(int j=i ; j < size2; j++)//找到与该元素存在相同的元素，将这个相同的元素交换到与该元素相同下标的位置上
{
if(array1[i] == array2[j])//第二种情况，找到了相等的元素
{
int tmp = array2[i];//对数组2进行交换
array2[i] = array2[j];
array2[j] = tmp;
swap = true;//设置标志
break;
}
}
if(swap != true)//第一种情况，没有相同元素存在时，将这个元素交换到尚未进行比较的尾部
{
int tmp = array1[i];
array1[i] = array1[--end];
array1[end] = tmp;
}
else
i++;
}
//结果就是在end表示之前的元素都找到了匹配，而end元素之后的元素都未被匹配
//先输出差集
cout<<"only in array1"<<endl;
for(i = end ; i < size1; i++)
{
cout<<array1[i]<<" ";
}
cout<<endl;
cout<<"only in array2"<<endl;
for(i = end ; i < size2; i++)
{
cout<<array2[i]<<" ";
}
cout<<endl;
//输出交集
cout<<"elements in array1 and array2"<<endl;
for(i = 0 ; i <end ; i++)
{
cout<<array1[i]<<" ";
}
cout<<endl;
//输出并集
cout<<"elements in array1 or array2"<<endl;
for(i = 0 ; i <end ; i++)
{
cout<<array1[i]<<" ";
}
for(i = end ; i < size1; i++)
{
cout<<array1[i]<<" ";
}
for(i = end ; i < size2; i++)
{
cout<<array2[i]<<" ";
}
cout<<endl;
}
输出结果如下：
only in array1
7 6 5 6 6 7
only in array2
1 3 2 4 8 9
elements in array1 and array2
6 1 2 5 4 3 5 5 3 4 2 3
elements in array1 or array2
6 1 2 5 4 3 5 5 3 4 2 3 7 6 5 6 6 7 1 3 2 4 8 9
Press any key to continue
最坏情况是n*n就是两个集合元素没有相同的情况，最好情况是两个集合元素全相同n。
所有当两个数组重复度较高的时候，使用这个算法会带来较高的效率。并且将集合的并集交集差集一并算出，仅使用O（1）附件空间复杂度。
还有人说使用排序数组然后二分查找，排序实际很耗时的。如果使用hash是很耗空间的。
本文转自：http://blog.sina.com.cn/s/blog_616e189f0100mrdn.html
二、数组内数据有序从小到大
#include <stdio.h>
bool join(const int *arrA, const int lenA, const int *arrB, const int lenB, \
int *arrDst, int *len)
{
int i = 0, j = 0, nCount = 0;
while (i < lenA && j < lenB)
{
if (arrA[i] == arrB[j])
{
//两个相等即交集
arrDst[nCount ++] = arrA[i];
i ++;
j ++;
}
else if(arrA[i] > arrB[j])
{
//移动小的数组index
j ++;
}
else
{
//移动小的数组index
i ++;
}
}
//交集的真实数目
*len = nCount;
return true;
}
bool merge(const int *arrA, const int lenA, const int *arrB, const int lenB, \
int *arrDst, int *len)
{
int i = 0, j = 0, nCount = 0;
while (i < lenA && j < lenB)
{
if (arrA[i] < arrB[j])
{
arrDst[nCount ++] = arrA[i];
//移动小的数组index
i ++;
}
else if(arrA[i] > arrB[j])
{
arrDst[nCount ++] = arrB[j];
//移动小的数组index
j ++;
}
else
{
arrDst[nCount ++] = arrA[i];
//相等只取一个
i ++;
j ++;
}
}
while(i < lenA)
{
arrDst[nCount ++] = arrA[i ++];
}
while(j < lenB)
{
arrDst[nCount ++] = arrB[j ++];
}
//并集的真实数目
*len = nCount;
return true;
}
void print(const int *arr, const int len)
{
int i;
printf("Data : ");
for(i = 0; i < len; ++ i)
{
printf("%2d ", arr[i]);
}
printf("\n\n");
}
void main()
{
int a[] = {0,1,3,5,7,8,9,10,11};
int b[] = {1,2,3,4,5,6,7,8,9,10,13,15,19};
int sizeA = sizeof(a) / sizeof(a[0]);
int sizeB = sizeof(b) / sizeof(b[0]);
int i = 0;
int j = 0;
int len;
int *c = new int [sizeA + sizeB];
printf("数组A和B的交集:\n");
join(a, sizeA, b, sizeB, c, &len);
print(c, len);
printf("数组A和B的并集:\n");
merge(a, sizeA, b, sizeB, c, &len);
print(c, len);
delete []c;
printf("\n\n");
}
三、3个已经排序的整数数列，找到common elements。
1）三个index指向三个数列开始，比较三者的值，若相等则找到一个。若有两个元素相等且较大，则较小的一个index+；其他情况，较小的两个index++。时间复杂度O(N)，N小于等于最长的数列长度。
2）先找两个数组的common element，过程和归并排序类似，然后看这个结果是否出现在数组三中即可，用二分查找。时间复杂度O(n)，空间复杂度为O(1)，如果是N个数组，则可以采用败者树。（新学习的，呵呵）