求两无序不重复数组的交集
//输入：a[]={5,7,8,9,1,2,3 }; b[]={2, 8,10,4,6,7};
//输出：{2,7,8}
[思路1]：
判断a数组元素值的元素是否在b中，是则输出之。
时间复杂度：O（n2）
void cmpInterSection(int a[], int b[], int m, int n)
{
for(int i = 0; i < m; i++)
{
for(int j = 0;j < n; j++)
{
if(a[i] == b[j])
{
cout << a[i] << "\t";
break;
}
}//end for j
}//end for i
cout << endl;
}
[思路2]：
1）对两数组进行排序；
2）一次循环判断a和b中元素是否相等，相等则输出；不等则小的值++。
时间复杂度：O（nlogn）
//快排之分割
int divided(int nArr[], int nLeft, int nRight)
{
int pivot = nArr[nLeft];
while(nLeft < nRight) //×¢ÒâwhileÑ»•
{
while(nLeft < nRight && nArr[nRight] >= pivot) //×¢ÒâµÈºÅ
{
--nRight;
}
nArr[nLeft] = nArr[nRight];
while(nLeft < nRight && nArr[nLeft] <= pivot) //×¢ÒâµÈºÅ
{
++nLeft;
}
nArr[nRight] = nArr[nLeft];
}
nArr[nLeft] = pivot;
return nLeft;
}
//快排之递归
void quickCurve(int nArr[], int nLeft, int nRight)
{
int nPivotPos = 0;
if(nLeft < nRight)
{
nPivotPos = divided(nArr,nLeft,nRight);
quickCurve(nArr,nLeft,nPivotPos-1);
quickCurve(nArr,nPivotPos+1,nRight);
}
}
//快排
void quickSort(int nArr[], int nLen)
{
quickCurve(nArr,0,nLen-1);
}
void interSectionOfArray(int a[], int b[], int m, int n)
{
//快排
quickSort(a,m);
quickSort(b,n);
//一次循环筛选出交集.
if( m < n)
{
int j = 0;
int i = 0;
while(i < m)
{
if(a[i] == b[j])
{
cout << a[i] << "\t";
i++;
j++;
}
else if(a[i] > b[j])
{
j++; //小值++
}
else
{
i++; //小值++
}
}
cout << endl;
}//end if
}
[思路3]：
hash表存储两数组到一个表中，统计次数累计为2的元素输出即可。
时间复杂度：O（n），典型的以空间换时间的方法。
ypedef struct HASHSET
{
int key; //值
int nCnt; //计数
}hashSet;
hashSet* pSetArray = new hashSet[m+n]; //空间换时间
for(int i = 0; i <m+n; i++)
{
pSetArray[i].key = 0;
pSetArray[i].nCnt = -1;
}
//O(n)实现输出…
void hashInterSection(hashSet* pSetArray, int a[], int b[], int m, int n)
{
for(int i = 0; i < m; i++)
{
pSetArray[a[i]].key = a[i];
pSetArray[a[i]].nCnt++;
}
for(int j = 0; j < n; j++)
{
pSetArray[b[j]].key = b[j];
pSetArray[b[j]].nCnt++;
}
for(int k = 0; k < m+n; k++)
{
if(pSetArray[k].nCnt == 1)
{
cout << pSetArray[k].key << "\t"; //两次累加-1+1+1=1.
}
}
cout << endl;
}
或者大家有什么更好的方法，欢迎讨论，谢谢！
[思路三]网友keynumber指出了存在问题，见下面的评论。笔者的思路三的确非常空间复杂度太高，且不是严格意义上的哈希表，只能算类哈希（呵呵）。
笔者进行了重写，如下：继续欢迎大家讨论。
//[修改后思路3]：构建哈希表插入操作的过程中，如果元素已经插入过，即其哈希地址有值，则该元素必为两数组的交集，打印输出即可。（前提数组中的元素不重复）
以下哈希表的构造是通过除留余数法实现的，处理冲突的方法是通过开放定址法实现的。
//初始设定表长10000.
const int g_nLength = 10000;
template <typename _Type>
class HashTable
{
public:
HashTable(int Length) //构建哈希表，表长Length
{
Element = new _Type[Length];
for(int i=0;i<Length;i++)
{
Element[i] = -1;
}
this->Length = Length;
Count = 0;
}
~HashTable()
{
delete[] Element;
}
//求哈希地址
virtual int Hash(_Type Data)
{
return Data % Length; //³ýÁôÓàÊý·¨Çó¹þÏ£µØÖ·.
}
//开放定址法再哈希
virtual int ReHash(int Index,int Count)
{
return ((Index + Count) % Length); //
}
//查找元素，若已存在返回true，否则返回false。
virtual bool SerachHash(_Type Data,int& Index)
{
Index = Hash(Data);
int Count = 0;
while(Element[Index] != -1 && Element[Index] != Data)
{
Index = ReHash(Index,++Count);
}
return (Data == Element[Index] ? true :false);
}
virtual int SerachHash(_Type Data)
{
int Index = 0;
if(SerachHash(Data,Index))
{
return Index;
}
else
{
return -1;
}
}
// 插入元素
bool InsertHash(_Type Data)
{
int Index = 0;
if(Count < Length && !SerachHash(Data,Index))
{
Element[Index] = Data;
Count++;
return true;
}
//在插入的过程中，如果元素已经存在，即为交集元素则打印之.
if(SerachHash(Data,Index))
{
cout << Data << "\t";
}
return false;
}
//手动设置表长
void SetLength(int Length)
{
delete[] Element;
Element = new _Type[Length];
for(int i=0;i<Length;i++)
{
Element[i] = -1;
}
this->Length = Length;
}
//移除元素.
void Remove(_Type Data)
{
int Index = SerachHash(Data);
if(Index != -1)
{
Element[Index] = -1;
Count--;
}
}
//清空整个哈希表
void RemoveAll()
{
for(int i=0;i<Length;i++)
{
Element[i] = -1;
}
Count = 0;
}
void Print()
{
for(int i=0;i<Length;i++)
{
printf("%d\t",Element[i]);
}
printf("\n");
}
protected:
_Type* Element; // Hash表
int Length; // Hash表长度
int Count; // Hash表当前长度
};
//自定义子类.
template <typename _Type>
class HashSet : public HashTable<_Type>
{
public:
HashSet(int nLen):HashTable<_Type>(nLen){}
~HashSet(){ }
friend void hashInterSection(HashSet<_Type>* pHashSet, int a[], int b[], int m, int n);
private:
};
//友元函数的实现
void hashInterSection(HashSet<int> *pHashSet, int a[], int b[], int m, int n)
{
for(int i = 0; i < m; i++)
{
pHashSet->InsertHash(a[i]);
}
for(int j = 0; j < n; j++)
{
pHashSet->InsertHash(b[j]);
}
cout << endl;
}
void main()
{
// HashSet<int> hashSet(20);
//测试用例1：两数组没有交集
// int a[]={10,9,8,15,14,16,7,33 };
// int b[]={1,3,5,11,13,17,19};
// int nLena = sizeof(a)/sizeof(a[0]);
// int nLenb = sizeof(b)/sizeof(b[0]);
// hashInterSection(&hashSet,a,b,nLena,nLenb);
// //用例1测试结果：返回空。
//测试用例2：两数组相等，所含元素全部相同。
// HashSet<int> hashSet2(20);
// int aa[]={10,9,8,15,14,16,7,33 };
// int bb[]={10,9,8,15,14,16,7,33 };
// int nLena = sizeof(aa)/sizeof(aa[0]);
// int nLenb = sizeof(bb)/sizeof(bb[0]);
// hashInterSection(&hashSet2,aa,bb,nLena,nLenb);
//用例2测试结果：返回交集。
//测试用例3：两数组部分相同。
HashSet<int> hashSet3(20);
int aa[]={10,9,8,15,14,16,7,33 };
int bb[]={10,9,8,15,144,166,73,333,55,29};
int nLena = sizeof(aa)/sizeof(aa[0]);
int nLenb = sizeof(bb)/sizeof(bb[0]);
hashInterSection(&hashSet3,aa,bb,nLena,nLenb);
//用例3测试结果：返回交集。
system("pause");
}
