在C++中比较两个数组的2个元素

Question

我有两个数组，每个数组都有一些值，例如：

int a[] =  {1, 2, 3, 4};
int b[] =  {0, 1, 5, 6};

现在我需要比较数组（a）中的元素和数组（b）中的元素。 如果有任何匹配，程序应返回错误或打印“错误，有重复值”等等。 在上述情况下，它应该返回一个错误，因为a [0] = b [1]，因为它们都具有相同的值。

我该怎么做呢？

- Desolator

---

这些数组是否已知为有序的？ - Ben Voigt

Answer 1

如果数组很小，我会采用暴力方法，循环遍历两个数组：

for (int i=0;i<4;++i)
{
    for (int j=0;j<4;++j)
    {
        if (a[i] == b[j])
        {
            // Return an error, or print "error there is a duplicate value" etc
        }
    }
}

如果你要处理大型数组，你可能需要考虑更好的算法，因为这个算法是O(n^2)。

例如，如果你的一个数组已经排序了，你可以更快地检查匹配项，特别是当数组的长度变得更长时。但是，如果你的数组始终只有几个元素，我不会费心去做任何更复杂的事情。

- Reed Copsey

---

+1 是为了提醒大家，这个算法具有二次复杂度，不适合处理大型数据集。 - stinky472

谢谢，我刚刚添加了标志并在循环后加入了if else语句，完成了 :) 谢谢。 - Desolator

Answer 2

假设两个数组已经排序好了，你可以按照下面这样的方式来遍历它们：

// int array1[FIRSTSIZE];
// int array2[SECONDSIZE];
for(int i=0, j=0; i < FIRSTSIZE && j < SECONDSIZE; ){
    if(array1[i] == array2[j]){
        cout << "DUPLICATE AT POSITION " << i << "," << j << endl;
        i++;
        j++;
    }
    else if(array1[i] < array2[j]){
        i++;
    }
    else{
        j++;
    }
}

这个应该具有线性复杂度，但仅在排序后才有效。

- Brendan Long

Answer 3

已经发布了有关排序数组的解决方案。如果数组未排序，则可以将每个数组构建为一个集合（例如std :: set或哈希集），并查看这些集合是否不相交。您可能需要在集合中存储值 - 索引对，以找出哪个索引是重复的（并适当地重载比较运算符）。这可能会导致O（n log n）复杂度。

- Philipp

---

我喜欢这个答案。需要注意的是：哈希集合在TR1中实现。std::tr1 :: unordered_set和boost :: unordered_set。TR1在GCC和Visual Studio中都有实现，因此std :: tr1 :: unordered_set应该足够“标准”。假设unordered_set一切正常，您应该能够以O（n）的时间复杂度完成此操作。 - Dragontamer5788

Answer 4

//v={1,2,3,4};  vector
//v1={1,2,3,4}  vector

  bool f=0;
    if(equal(v.begin(),v.end(),v1.begin()))  //compare two vector, if equal return true
    {
        f=1;
    }

    }
    if(f==1)
        cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

        enter code here

- asad_IT