algorithm - pseint - cómo combinar dos matrices de enteros ordenados en su lugar utilizando el tiempo O(n) y el costo de espacio O(1)

ejercicios resueltos de arreglos en pseint

Question

Por ejemplo, dada una matriz de enteros y la posición de inicio de sus dos secuencias consecutivas que son ''b1'' y ''b2'', además se proporciona la posición ''última'' que indica la posición final de la segunda secuencia. ¿Desde la matriz [b1] a la matriz [b2-1] y desde la matriz [b2] a la matriz [última] están en orden por separado, cómo combinarlas en su lugar utilizando el tiempo O (n) y el costo de espacio O (1) ?

Answer 1

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);
    }
}

Answer 2

Aunque no es completamente posible en O(n) , tengo una propuesta para hacerlo más rápido que O(n^2) . Uso solo el espacio O(1) que es la temperatura 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;
    }

Answer 3

Esto no es de ninguna manera un problema simple. Es posible, pero rara vez se hace en la práctica porque es mucho más complicado que una combinación estándar utilizando el espacio N-scratch. El artículo de Huang y Langston ha existido desde finales de los años 80, aunque las implementaciones prácticas realmente no surgieron hasta más tarde. Anteriormente, el trabajo de L. Trabb-Prado en 1977 es anterior a Huang y Langston de manera significativa, pero me desafió a encontrar el texto exacto de ese documento; sólo abundan las referencias.

Una excelente publicación posterior, Combinación in situ asintóticamente eficiente (1995) por Geert, Katajainenb y Pasanen es una buena cobertura de algoritmos múltiples, y hace referencia a las contribuciones de Trabb-Prado al tema.

Answer 4

Hay cosas tales como verdaderas fusiones en el lugar, pero no son lo suficientemente claras como para que alguien las reinvente de forma independiente en medio de una entrevista; ha habido artículos que describen una sucesión de algoritmos bastante complejos durante años. Una es la fusión práctica en el lugar, por Huang y Langston, CACM, marzo de 1988. La idea inicial para esto es dividir los datos de longitud n en bloques de tamaño sqrt (n), y usar un bloque, lleno de los elementos más grandes de Los datos, para proporcionar espacio de búfer utilizado en la fusión de los otros. La introducción a ese papel dice

"Dadas dos listas ordenadas cuyas longitudes suman n, los métodos obvios para fusionarse en los pasos O (n) también requieren una cantidad lineal de memoria adicional. Por otra parte, es fácil combinar en su lugar usando solo una cantidad constante de espacio adicional por clasificación en montón, pero a un costo de tiempo O (n log n) "

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

Answer 5

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

Divide ambas partes de la matriz en bloques de tamaño k = sqrt (n). Ordena los bloques usando sus primeros elementos como base para la comparación. Esto se puede hacer en sqrt (n) ^ 2 = O (n) por orden de selección. La propiedad clave 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 "ordenados erróneamente" debajo de ella, es decir, elementos en las posiciones j < i , de manera que A[j]>A[i] . Estos están (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 de él) ya están ordenados correctamente en relación con A[i] debido a que los bloques están ordenados en sus primeros elementos. Esta es la razón por la que la segunda fase funciona, es decir, logra la matriz completamente ordenada:

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

Answer 6

Tuve una entrevista (con una compañía muy importante) hace un par de horas y me preguntaron eso. Ahí está la 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--;
     }
}