兩個排序數組的相交

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解決方案。當其他循環向前移動時，嘗試在其中一個循環中尋找單調性。如果你發現，你已經找到了你的優化。快樂編碼:)