c++ - 两个数组之间的共同功能？

Question

我想找到两个数组之间的公共(public)元素。我的功能无法正常工作。数组被排序。只想将两个排序数组放入 check_common 函数中以显示公共(public)元素。任何人都可以帮助修复它!

void check_common (int x[], int size1, int y[], int size2)
    {
        int temp;
cout << " Common elements are:\t" << endl;
for ( int i=0; i <= size2; i++ )
{
    for ( int j=0; j <= size1; j++)
    {
        if (x[j] == y[j]){
            temp = x[j];
            cout << temp << "\t";}
    }   
}
cout << endl;
    }

Answer 1

如果任一数组中的项目不唯一，您的解决方案就会失败，因为所有其他元素都已移动。

天真的解决方案是使用 O(n) 检查。检查 array1 中的每个元素是否也存在于 array2 中。由于列表已排序，因此执行此检查的时间复杂度为 O(log(n))。因此，总体运行时间将为 O(nlog(n))，这还算不错。如果你能保证每个列表项都是唯一的，它可以在 O(log(n)) 中完成。