本帖最后由 呐咯密密 于 2022-8-23 09:27 编辑
求三个数组的共同元素
给定三个含有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中做二分搜索。
代码// 找出三个数组的共同元素
// 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中进行二分搜索，但是这样做是有问题的，你看出来了么？ 代码// 找出三个数组唯一的共同元素
// 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
}
// Determine whether a contains value k
bool BinarySearch(int *a, int n, int k)
{
int left = 0 ;
int right = n - 1 ;
while (left <= right)
{
int mid = (left + right) ;
if(a[mid] < k)
left = mid + 1 ;
if(a[mid] == k)
return true ;
else
right = mid - 1 ;
}
return false ;
}
// Compare function for qsort
int compare(const void* a, const void* b)
{
return *(int*)a - *(int*)b ;
}
小小总结一下，对于在数组中进行查找的问题，可以分如下两种情况处理 如果能做到以上两点，大多数关于数组的查找问题，都能迎刃而解。
|
楼主
标题置顶
标题高亮
