Как объединить 2 частично отсортированных массива?

Question

Дано 2 массива с int, A1 и A2. Длина A1 равна L1, длина A2 равна L1 + L2. Первые элементы L2 A1 и A2 были отсортированы. Объедините первые элементы L2 в A2. например

   A1:  1  3  6  0
   A2:  2  5  7  13  10 22 11 
   result: 
   A1 + A2:  1 2 3 5 6 7 13 10 22  11

мои решения:

Выберите каждый элемент, поместив min {A1 [i], A2 [i]} в массив B [i], O (2 * L2) Скопируйте B в A2. O (L1 + L2).

Несортированная деталь не должна быть изменена.

Есть ли лучшие решения?

спасибо

Answer 1

int* semiMerge(int*, int, int*, int);

int main() {
  const int A1[] = {1, 3, 6, 0};
  const int A2[] = {2, 5, 7, 13, 10, 22, 11};

  const int L1 = sizeof(A1)/sizeof(int);
  const int L2 = sizeof(A2)/sizeof(int) - L1;

  int* out = semiMerge(A1, L1, A2, L2);
}

int* semiMerge(A1, L1, A2, L2) {
  int* output = new int[L2 + L2 + L1];

  //merge does a sorted combination of the items--both sets must be sorted up to the endpoints;
  //we want to merge only the first L1 results from each array
  std::merge(A1, A1 + L2,
             A2, A2 + L2,
             output);
  //at this point, we have an array of 2*L1 elements, all sorted properly.


  //we want to start looking at the first element we didn't copy from A2,
  //the -1 is to account for the fact that begin() + L1 is the start of the L1+1th slot
  std::copy(A2 + L2,
            A2 + L2 + L1, 
            (output + L2 + L2 - 1));

return output;
}

Я решил показать A1 и A1 как статические массивы, но если вы получаете их как int* s для массивов, выделенных в куче, и если важно, чтобы готовый массив был помещен в L2, вы можете сказать delete[] L2; L2 = out; после звонка на semiMerge(). Я решил не делать этого в основном, потому что я представлял A2 как статический массив, в то время как переключение его на содержимое out потребовало бы, чтобы он был указателем на динамический массив.

Answer 2

Теперь, когда я выяснил, что такое L1 и L2:

{
    std::vector<int> B(L2+L2+L1, 0);
    std::merge(A1.begin(), A1.begin()+L2, A2.begin(), A2.begin()+L2, B.begin());
    if (L1 > L2)
        B.insert(B.end(), A2.begin()+L2, A2.end());
    A2.swap(B);
}

B содержит [объединенную отсортированную часть] [несортированный A2]. Это правильный формат? Это алгоритм, который вы опубликовали. На месте (как Nim) медленнее, но использует меньше памяти, так что это компромисс.

Answer 3

1. Копирование A1 и A2 в один массив
2. std :: inplace_merge с началом, началом + L2, концом

(ну, вы не указали никаких библиотечных функций!);)

Это звучит как домашнее задание, и я обычно стесняюсь, прежде чем предоставить код для домашнего задания.Однако, похоже, здесь необходим пример:

std::vector<int> A1; // initialize to { 1  3  6  0 }
std::vector<int> A2; // initialize to { 2  5  7  13  10 22 11 }

// Now assumption here is that we want L2 items from A1, so let's copy
A2.insert(A2.begin(), A1.begin(), A1.begin() + L2);

// Now A2 contains the sorted range from A1 0 is dropped (?)
// Now call inplace_merge, this leaves the unsorted segment of A2 alone, and only includes
// L2 items from A2.
std::inplace_merge(A2.begin(), A2.begin() + L2, A2.begin() + (2*L2));