新浪博客

求两个数组的交集、并集和差集算法分析与实现

2010-11-08 19:23阅读：

http://blog.sina.cn/dpool/blog/u/1634605215

本文采用一种交换的方式来求出两个数组的并集，交集和差集，这种算法运算速度较快，内存消耗空间较少，是一个值得学习的好方法，另外，作者提醒您，重要的不是算法本身，而是该算法会开拓我们的思维空间，要注意对问题的多思考。

算法概述：
两个任意元素的数组，比较出两个数组中相同的元素和不同的元素。

元素划分：
计算过程中，两个数组内部元素的划分：

求两个数组的交集、并集和差集算法分析与实现

算法流程：
从数组1的尚未比较的元素中拿出第一个元素array1(i)，用
array1(i)与array2(j)进行比较（其中j>i且j<array2的长度），可能出现下面两种情况，
1． 数组2中找到了一个与array1(i)相等的元素，则将array2(j)与array2(i)进行交换，i加一，进行下次迭代
2． 数组2直到结尾也没找到与array1(i)相等的元素，则将array1(i)与尚未进行比较的最后一个元素array1(k)进行交换，i不加一，进行下次迭代。

算法实现代码：
#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 = 18;
int array2[] = {8,2,1,3,4,5,3,2,4,5,3,2,1,3,5,4,6,9};
int size2 = 18;
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++)
{

我的更多文章

下载客户端阅读体验更佳

APP专享