En lugar de combinación de dos matrices

Question

Tenemos una matriz de tamaño m + n en el que m elementos son presente, en orden clasificado, y una segunda matriz de tamaño n, de nuevo en orden clasificado. Nosotros queremos que ambos estén ordenados y presentes en la primera matriz. No se supone que se proporcione una tercera matriz .

Ejemplo:

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

La respuesta sería:

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

Answer 1

Realice una fusión regular, pero en orden inverso, comparando primero los números más grandes, almacenando (invirtiendo) en el extremo de la primera serie que se mueve hacia atrás. De esta forma, los elementos que está fusionando nunca se sobrescriben (que esto funciona es fácil de ver si lo piensa por un momento).

Answer 2

mover el contenido de la primera matriz al final de la primera matriz, de tal manera que los elementos vacíos son ahora al comienzo . A continuación, combine las dos secuencias como de costumbre en la primera matriz.

Answer 3

En el lugar requiere básicamente que solo usemos la cantidad de memoria "constante", que no cambia con diferentes tamaños de matriz de entrada. Sin embargo, la pregunta misma asigna una cantidad extra de memoria que es igual al tamaño de una de las dos matrices de entrada, que es la memoria O (n) en el peor de los casos. Básicamente, esto hace que la idea de "in-situ" sin sentido ...

La pregunta podría ser mejor expresar como "fusionar sin memoria adicional", que es una descripción más precisa de su verdadera intención ...

Answer 4

// 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[] 
     } 
     } 
    }