两个排序数组的相交

Question

问题>给定两个排序数组A和B，返回一​​个数组C，其中包含A和B共有的元素。数组C不能包含重复项。

这是我的解决方案，但我的直觉是它是错误的。但是我找不到反证的反例。 有人可以为我指出吗？或者给我一个反例呢？

更新：

该算法的工作原理如下：

我们坚持一个指针，每个阵列和，直到我们找到一个共同的因素推动这些指针。然后，如果公共元素不在C中，则找到的元素将存储在C中。否则，根据元素，我们相应地将指针向前移动。

#include <iostream> 
#include <vector> 
#include <random> 
#include <iterator> 
#include <algorithm> 
using namespace std; 

vector<int> Intersect(const vector<int>& vecIntsA, const vector<int>& vecIntB) 
{ 
    int indA = 0; 
    int indB = 0; 
    vector<int> vecIntC; 

    while(indA < vecIntsA.size() && indB < vecIntB.size()) 
    { 
     if (vecIntsA[indA] == vecIntB[indB]) { 
      if (vecIntC.empty() || vecIntC.back() != vecIntsA[indA]) 
       vecIntC.emplace_back(vecIntsA[indA]); 
      indA++; 
      indB++; 
     } else if (vecIntsA[indA] < vecIntB[indB]) 
      indA++; 
     else // (vecIntsA[indA] > vecIntB[indB]) 
      indB++;   
    } 

    return vecIntC; 
} 

int main() 
{ 
    default_random_engine dre; 
    uniform_int_distribution<int> dist(0, 100); 

    vector<int> vecIntA; 
    for(int i=0; i < 20; ++i) 
    vecIntA.emplace_back(dist(dre)); 
    sort(vecIntA.begin(), vecIntA.end()); 
    copy(vecIntA.cbegin(), vecIntA.cend(), ostream_iterator<int>(cout, ",")); 
    cout << endl; 

    vector<int> vecIntB; 
    for(int i=0; i < 24; ++i) 
    vecIntB.emplace_back(dist(dre)); 
    sort(vecIntB.begin(), vecIntB.end()); 
    copy(vecIntB.cbegin(), vecIntB.cend(), ostream_iterator<int>(cout, ",")); 
    cout << endl; 

    vector<int> vecIntC = Intersect(vecIntA, vecIntB); 
    copy(vecIntC.cbegin(), vecIntC.cend(), ostream_iterator<int>(cout, ",")); 

    return 0; 
} 

Answer 1

你总是可以使用STL算法set_intersection和唯一的？

Answer 2

你的算法看起来很合理。对于它的价值，我最近解决了完全相同的问题，并提出了a similar algorithm两个阵列的长度相似的情况。一般来说，如果您想支持您的算法产生良好解决方案的信念，请使用可以自动检查的方式表达优质解决方案的基本属性。然后针对这些属性编写自动化测试。 （这被测试的一个很大的样式由QuickCheck普及。）

对于这个问题，例如，就表达阵列相交的基本属性，如下所示：“给定的交叉功能f，对于所有的排序阵列A和B， f(A, B) == sorted(set(A) & set(B))“。 （在Python中，set(xs)从xs生成一个集合，并且应用于集合的&运算符计算交集）。本质上，我将数组交集的期望语义映射到Python的内置语义以排序和设置交集。这样一来，我就可以用廉价易用的部件为我的实施建立一个正确性预言。最后一步是构造随机测试用例并检查映射是否持有（通过咨询oracle）。

这里的相应的代码：

def check_function(f): 
# fundamental property: 
# forall sorted arrays A, B. intersect(A, B) == sorted(set(A) & set(B)) 
from math import factorial 
from random import randrange 
from nose.tools import assert_equal 
for N in xrange(8): 
    for _ in xrange(factorial(N)): # get decent sample of problem space 
     m, n = randrange(N + 1), randrange(N + 1) 
     A = sorted(randrange(N + 1) for _ in xrange(m)) 
     B = sorted(randrange(N + 1) for _ in xrange(n)) 
     got = f(A, B) 
     expected = sorted(set(A) & set(B)) 
     assert_equal(got, expected) 

Answer 3

这里是时间复杂度（P + Q），其中p和q分别是阵列A和B的长度，一个快速的解决方案。

#include <iostream> 
#include <vector> 
#include <set> 
#include <algorithm> 
using namespace std; 

set<int> intersect(vector<int> &A, vector<int> &B) { 
    int j = 0; 
    vector<int> V; 
    for(int i = 0;i<A.size();i++){ 
     first: 
     if(j == B.size()) break; 
     if(A[i] == B[j]){ 
      V.push_back(A[i]); 
      j++; 
     } 
     else if(A[i]>B[j]) { j++;goto first;} 
    } 
    set<int> S(V.begin(), V.end()); 
    return S; 
} 

int main() { 
    vector<int> A,B; 
    A = {1,2,3,3,4,5,6}; 
    B = {3,3,5,6}; 
    set<int> S; 
    S = intersect(A,B);  
    set<int>::iterator iter; 
    for(iter=S.begin(); iter!=S.end();++iter){ 
     cout<<(*iter)<<" "; 
    } 

    return 0; 
} 

这是一个2-pointer解决方案。当其他循环向前移动时，尝试在其中一个循环中寻找单调性。如果你发现，你已经找到了你的优化。快乐编码:)