另外，上面的方法，只要b有序即可，a是否有序无所谓，因为我们只是在b中做Binary Search。如果a也有序的话，那么再用上面的方法就有点慢了，因为如果a中某个元素在b中的位置是k的话，那么a中下一个元素在b中的位置一定位于k的右侧，所以本次的搜索空间可以根据上次的搜索结果缩小，而不是仍然在整个b中搜索。也即如果a和b都有序的话，代码可以做如下修改，记录上次搜索时b中元素的位置，作为下一次搜索的起始点。
求三个数组的共同元素
给定三个含有n个元素的整型数组a,b和c，求他们最小的共同元素。
如果三个数组都有序，那么可以设置三个指针指向三个数组的头部，然后根据这三个指针所指的值进行比较来移动指针，直道找到共同元素。
// 三个数组的共同元素-只找最小的
void FindCommonElements(int a[], int b[], int c[], int x, int y, int z)
{
for(int i = 0, j = 0, k = 0; i < x && j < y && k < z;)
{
if(a[i] < b[j])
{
i++ ;
}
else // a[i] >= b[j]
{
if(b[j] < c[k])
{
j++ ;
}
else // b[j] >= c[k]
{
if(c[k] < a[i])
{
k++ ;
}
else // c[k] >= a[i]
{
cout << c[k] << endl ;
return ;
}
}
}
}
cout << "Not found!" << endl ;
}
如果三个数组都无序，可以先对a, b进行排序，然后对c中任意一个元素都在b和c中做二分搜索。
// Find the unique common element in 3 arrays
// O(NlogN)
int UniqueCommonItem(int *a, int *b, int *c, int n)
{
// sort array a
qsort(a, n, sizeof(int), compare) ; // NlogN
// sort array b
qsort(b, n, sizeof(int), compare) ; // NlogN
// for each element in array c, do a binary search in a and b
// This is up to a complexity of N*2*logN
for (int i = 0; i < n; i++)
{
if(BinarySearch(a, n, c[i]) && BinarySearch(b, n, c[i]))
return c[i] ;
}
return - 1 ; // not found
}
也可以对a进行排序，然后对于b和c中任意一个元素都在a中进行二分搜索。
// Find the unique common element in 3 arrays
// O(NlogN)
int UniqueCommonItem1(int *a, int *b, int *c, int n)
{
// sort array a
qsort(a, n, sizeof(int), compare) ; // NlogN
// Space for time
bool *bb = new bool[n] ;
memset(bb, 0, n) ;
bool *bc = new bool[n] ;
memset(bb, 0, n) ;
// for each element in b, do a BS in a and mark all the common element
for (int i = 0; i < n; i++) // NlogN
{
if(BinarySearch(a, n, b[i]))
bb[i] = true ;
}
// for each element in c, do a BS only if b[i] is true
for (int i = 0; i < n; i++) // NlogN
{
if(b[i] && BinarySearch(a, n, c[i]))
return c[i] ;
}
return - 1 ; // not found
}
排序和二分搜索代码如下：
