cómo fusionar dos matrices de enteros ordenadas en su lugar utilizando el tiempo O (n) y el costo de espacio O (1)

Por ejemplo, dado un conjunto de enteros y la posición inicial de sus dos secuencias consecutivas que son ‘b1’ y ‘b2’, además se proporciona la posición ‘último’ que indica la posición final de la segunda secuencia. Desde el conjunto [b1] al conjunto [b2-1] y del conjunto [b2] al conjunto [último], ambos están en orden por separado, ¿cómo combinarlos en su lugar utilizando el tiempo O (n) y el costo de espacio O (1) ?

La fusión de Kronrod fue el primer algoritmo publicado para hacer eso. Va más o menos así:

Divida ambas partes de la matriz en bloques de tamaño k = sqrt (n). Ordene los bloques usando sus primeros elementos como base para la comparación. Esto se puede hacer en sqrt (n) ^ 2 = O (n) por selección de ordenación. La propiedad clave de la ordenación de selección aquí es que tiene movimientos constantes por bloque, por lo que solo #comparisons es cuadrado.

Después de esta fase, para cada elemento A[i] en la matriz hay como máximo k-1 elementos “clasificados incorrectamente” debajo de ella, es decir, elementos en las posiciones j < i tales que A[j]>A[i] . Estos son (posiblemente) en el bloque más cercano debajo de él que proviene de la otra parte fusionada. Tenga en cuenta que el primer elemento del bloque (y todos los demás bloques debajo) ya están correctamente ordenados en relación a A[i] debido a que los bloques están ordenados en sus primeros elementos. Esta es la razón por la cual la segunda fase funciona, es decir, logra la matriz ordenada por completo:

Ahora combine el primer bloque con el segundo, luego el segundo con el tercero, etc., usando los últimos 2 bloques como espacio temporal para la salida de la combinación. Esto codificará el contenido de los dos últimos bloques, pero en la última fase (junto con el bloque anterior) se pueden ordenar por selección ordenar en sqrt (n) ^ 2 = O (n) tiempo.

Hay cosas tales como verdaderas fusiones en el lugar, pero no son lo suficientemente sencillas como para que alguien las reinvente independientemente en el medio de una entrevista: ha habido documentos que describen una sucesión de algoritmos bastante complejos para esto durante años. Una es la Fusión Práctica en el Lugar, por Huang y Langston, marzo de 1988. La idea inicial es dividir los datos de longitud n en bloques de tamaño sqrt (n), y usar un bloque, rellenado con los elementos más grandes de los datos, para proporcionar espacio de búfer utilizado en la fusión de los demás. La introducción a ese documento dice

“Dadas dos listas ordenadas cuyas longitudes se sumn a n, los métodos obvios para fusionarse en O (n) pasos requieren también una cantidad lineal de memoria adicional. Por otro lado, es fácil fusionarse en su lugar utilizando solo una cantidad constante de espacio adicional por clasificación de montón, pero a un costo de O (n log n) tiempo ”

Por lo tanto, afirmo que la verdadera fusión en el lugar puede hacerse, pero no es obvia.

Aunque no es posible por completo en O(n) tiempo, tengo una propuesta para hacerlo más rápido que O(n^2) . Uso solo O(1) espacio que es temporal en mi código. Estoy seguro de que debería funcionar mejor que O(n^2) .

 private static int[] mergeSortedArrays(int[] a1, int[] a2) { int i = 0, j = 0; while (a1[i] != Integer.MIN_VALUE) { if (a1[i] > a2[j]) { int temp = a1[i]; a1[i] = a2[j]; a2[j] = temp; for (int k = 1; k < a2.length; k++) { if (a2[k - 1] > a2[k]) { temp = a2[k - 1]; a2[k - 1] = a2[k]; a2[k] = temp; } } } i++; } while(j < a2.length){ a1[i++] = a2[j++]; } return a1; } 

Aquí está la memoria O (n-1) (n + 1)

 /** * Created by deian on 2016-12-22. * We just need track the two smallest numbers */ public class Merge { public static void swap(int[] a, int i1, int i2) { int t = a[i1]; a[i1] = a[i2]; a[i2] = t; } public static void merge(int[] a) { // i1 and i2 - always point to the smallest known numbers // it would works as well with two m and n sized arrays int i1 = 0; int i2 = a.length / 2; System.out.printf(" %s, i(%d,%d) \n", Arrays.toString(a), i1, i2); for (int di = 0; di < a.length - 1; di++) { int ni; int oi1 = i1; int oi2 = i2; if (a[i1] > a[i2]) { ni = i2; i2++; if (i2 >= a.length) { i2--; } } else { ni = i1; i1++; if (i1 >= i2) { i1 = di; } } if (di == i1) { i1 = ni; } swap(a, di, ni); System.out.printf("#%d: %s, i(%d,%d)s(%d>%d)i(%d,%d) \n", di + 1, Arrays.toString(a), oi1, oi2, ni, di, i1, i2); } System.out.printf(" %s\n", Arrays.toString(a)); } public static void main(String[] args) { // int[] a = new int[]{1, 3, 6, 8, -5, -2, 3, 8}; // int[] a = new int[]{1, 3, 6, 8, -5, 2, 3, 8}; // int[] a = new int[]{1, 5, 6, 8, -5, 2, 3, 4}; // int[] a = new int[]{1, 5, 6, 8, -5, -2, -1, 4}; // int[] a = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8}; // int[] a = new int[]{5, 6, 7, 8, 1, 2, 3, 4}; int[] a = new int[]{1, 3, 5, 7, 2, 4, 6, 8}; merge(a); } } 

Tuve una entrevista (con una compañía muy importante) hace un par de horas y me preguntaron eso. Hay una respuesta en Java

 public static void main(String[] args) { int A[] = { 1, 3, 5, 6, 9 }; int B[] = new int[12]; B[0] = 3; B[1] = 6; B[2] = 8; B[3] = 10; B[4] = 11; B[5] = 13; B[6] = 15; mergeInB(A, B, 7); for (int n : B) System.out.print(n + " "); } /** * @param a * @param b - it will be modified * @param j = length of b */ public static void mergeInB(int[] a, int[] b, int j) { int i = a.length - 1, k; j --; for (k = b.length-1; k >= 0; k--) { if (i >= 0 && j >= 0) { if (a[i] > b[j]) { b[k] = a[i]; i --; } else { b[k] = b[j]; j --; } } else break; } while(i>=0 && k >=0) { b[k] = a[i]; k --; i --; } while(j>= 0 && k >=0) { b[k] = b[j]; j--; k--; } }