Поиск объединения 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 пуст, поэтому я все равно вставляю 1 элемент в unionVector. Я бы очень признателен, если кто-нибудь может предложить способ, которым я могу выполнить эту проверку, не вставляя сначала один элемент (я думал о наличии переменной флага, которая проверяет, является ли unionVector пустым или нет, но я чувствую, что это будет слишком грязно)

Edit 1:

• Это не проблема домашних заданий. Это то, что я практиковал для своих интервью

Изменить 2:

• Я также не могу использовать любые встроенные функции

Edit 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, чтобы сохранить дубликаты.