Объединение двух массивов по месту

Question

У нас есть массив размером m + n , в котором присутствуют m элементы в отсортированном порядке, и второй массив размером n , опять жев отсортированном порядке.Мы хотим, чтобы они оба были отсортированы и представлены в первом массиве.Третий массив не должен быть задан.

Пример:

   1, 3, 55, 66, 77, _, _, _ 
   5, 9, 20 

Ответ будет:

   1, 3, 5, 9, 20, 55, 66, 77 

Answer 1

Выполняйте регулярную сортировку слиянием, но сначала сравнивайте сначала самые большие числа, сохраняя (переворачивая) в конце первого массива, возвращаясь назад. Таким образом, элементы, которые вы объединяете, никогда не перезаписываются (это легко увидеть, если вы подумаете об этом на мгновение).

Answer 2

    // merge the elements in B[] to A[], starting from the last one
    void merge(int A[], int m, int B[], int n) {
       // m-1 and n-1 represent the current element index in A[] and B[] respectively
      while (n > 0) { // there are still elements in B[] not merged
          if (m > 0 && A[m-1] > B[n-1]) { // current element in A[] > current element in B[]
            A[m+n-1] = A[m-1]; // move current element of A[] to its right position
            --m; // decrease current element index of A[]
          }
         else { // current element in A[] <= current element in B[]
            A[m+n-1] = B[n-1]; // move current element in B[] to its right position
            --n; // decrease current element index of B[]
         }
      }
   }

Answer 3

На месте в основном требуется, чтобы мы использовали только «постоянный» объем памяти, который не изменяется при разных размерах входного массива.Однако сам вопрос выделяет дополнительный объем памяти, равный размеру одного из двух входных массивов, который в худшем случае равен O (n) памяти.Это в основном делает идею «на месте» бессмысленной ...

Вопрос может быть лучше сформулирован как «слияние без дополнительной памяти», что является более точным описанием его реального намерения ...

Answer 4

Переместить содержимое первого массива в конец первого массива, чтобы пустые элементы теперь были в начале.Затем объедините две последовательности, как обычно, в первый массив.