查找2個排序數組的聯合（重複）

Question

我試圖找到2個排序數組的聯合（重複），但我覺得我沒有拿出最優雅的代碼（我有工作順便說一句，我只是覺得我可以減少一些代碼行）。可以說我有2個向量a = {1,3,3,4,4,4,5,7}和b = {1,3,3,3,5,5,5,6,8,9}和我想他們的聯合存儲在一個名爲unionVector矢量（這將是1,3,4,5,6,7,8,9）

這裏是我的代碼：

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

// Prints the contents of a vector 
void printVector(vector<int> a){ 
    if(a.size() == 0) 
    return; 
    else{ 
    for(int i = 0; i < a.size(); i++) 
     cout << a[i] << '\t'; 
    } 
    cout << endl; 
} 

// Print the union of 2 sorted arrays with duplicates 
void printUnion(int *a, int aSize, int *b, int bSize){ 
    if(aSize == 0 && bSize == 0) 
    return; 
    else{ 

    vector<int> unionVector; 

    int i = 0; 
    int j = 0; 
    int last = 0; 

    // insert the smaller of first element regardless 
    if(a[i] < b[j]){ 
     unionVector.push_back(a[i]); 
     i++; 
    } 
    else if (b[j] < a[i]){ 
     unionVector.push_back(b[j]); 
     j++; 
    } 
    else{// both are equal numbers 
     unionVector.push_back(a[i]); 
     i++; 
     j++; 
    } 

    // now traverse both the loops one increment at a time 
    while(i < aSize && j < bSize){ 
     last = unionVector[unionVector.size() - 1]; 

     if(a[i] < b[j]){ 
     if(last != a[i]) 
      unionVector.push_back(a[i]); 
     i++; // increment i in either case 
     } 
     else if(b[j] < a[i]){ 
     if(last != b[j]) 
      unionVector.push_back(b[j]); 
     j++; 
     } 
     else{ 
     // both of the numbers are equal 
     if(last != a[i]) 
      unionVector.push_back(a[i]); 
     i++; 
     j++; 
     } 
    } 

    // lets say if 1 array wasn't complete 
    while(i < aSize){ 
     last = unionVector[unionVector.size() - 1]; 

     if(last != a[i]) 
     unionVector.push_back(a[i]); 
     i++; 
    } 

    while(j < bSize){ 
     last = unionVector[unionVector.size() - 1]; 

     if(last != b[i]) 
     unionVector.push_back(b[j]); 
     j++; 
    } 

    printVector(unionVector); 
    } 
} 

int main(){ 
    int a[] = {1,3,3,4,4,4,5,7}; 
    int b[] = {1,3,3,3,5,5,5,6,7,7,8,9}; 

    printUnion(a,8,b,12); 

    return 0; 
} 

事情是因爲可以重複我檢查要插入unionVector中插入最後一個元素的元素。我需要確保當unionVector爲空時我不會嘗試獲取'last'元素，這就是爲什麼我無論如何都要在unionVector中插入1個元素。我真的很感激，如果任何人都可以提出一種方法，我可以做這個檢查，而不需要先插入一個元素（我想有一個標誌變量來檢查unionVector是否爲空，但我覺得這太麻煩了）

編輯1：

• 這不是一個作業問題。這是我在練習我的採訪

編輯2：

• 我也不能使用任何內置函數

編輯3：

• 一些如果這是C++的立場，人們會感到困惑。你可以使用任何你想要的語言

Answer 1

如果兩個數組都被排序，那麼只需要在一個迭代器或另一個或兩者之間跳過，如果匹配的話。

因此，像：

void printUnion(int* a, int aSize, int* b, int bSize) 
{ 
    int *aEnd = a + aSize, *bEnd = b + bSize; 
    std::vector<int> unionVec; 

    for (; a != aEnd;) { 
     if (b == bEnd) { 
      // copy all of a 
      while (a != aEnd) { 
       unionVec.push_back(*a); 
       a = std::upper_bound(a + 1, aEnd, *a); 
      } 
      break; 
     } 

     if (*b < *a) { 
      unionVec.push_back(*b); 
      b = std::upper_bound(b + 1, bEnd, *b); 
     } 
     else { 
      unionVec.push_back(*a); 
      if (*b == *a) { 
       b = std::upper_bound(b + 1, bEnd, *b); 
      } 
      a = std::upper_bound(a + 1, aEnd, *a); 
     } 
    } 

    // copy all of b 
    while (b != bEnd) { 
     unionVec.push_back(*b); 
     b = std::upper_bound(b + 1, bEnd, *b); 
    } 

    printVector(unionVec); 
} 

如果你不能直接使用upper_bound，只是自己實現該功能。複製從this reference實現：

template<class ForwardIt, class T> 
int* upper_bound(int* first, int* last, const int value) 
{ 
    int* it; 
    int count = last - first; 
    int step; 

    while (count > 0) { 
     it = first; 
     step = count/2; 
     it += step; 
     if (value >= *it) { 
      first = ++it; 
      count -= step + 1; 
     } 
     else { 
      count = step; 
     } 
    } 

    return first; 
} 

或者非二進制搜索版本：

int* upper_bound(int* first, int* last, const int value) { 
    for (; first < last && *first == value; ++first) { 
     ; 
    } 

    return first; 
} 

現在顯然很囉嗦了，這就是爲什麼標準實際上是你直接提供的算法set_union：

void printUnion(int* a, int aSize, int* b, int bSize) 
{ 
    std::vector<int> unionVec; 

    // get the union 
    std::set_union(a, a + aSize, b, b + bSize, std::back_inserter(unionVec)); 

    // remove the dupes 
    unionVec.erase(std::unique(unionVec.begin(), unionVec.end()), unionVec.end()); 

    printVector(unionVec); 
} 

Answer 2

這是一種方法。優雅可能會有所不同！

void printUnion(int* a, int aSize, int* b, int bSize) 
{ 
    std::multiset<int> x; 
    x.insert(a, a + aSize); 
    x.insert(b, b + bSize); 

    for (auto y : x) 
     cout << y << ","; 
    cout << endl; 
} 

NB。考慮讓printUnion採用迭代器對。使用std::set忽略重複項，或使用std::multiset保留重複項。