arrays - una - Encontrar el número más pequeño en orden de n arreglos ordenados

numero mayor de una lista java

Question

Por lo tanto, tiene n arreglos ordenados (no necesariamente de la misma longitud), y debe devolver el kth elemento más pequeño en el arreglo combinado (es decir, el arreglo combinado formado al combinar todos los arreglos ordenados n)

Lo he estado probando y sus otras variantes durante bastante tiempo, y hasta ahora solo me siento cómodo en el caso de que haya dos matrices de igual longitud, ambas ordenadas y una tiene que devolver la mediana de estas dos. Esto tiene complejidad logarítmica en el tiempo.

Después de esto, traté de generalizarlo para encontrar kth más pequeño entre dos arreglos ordenados. Here está la pregunta sobre SO. Incluso aquí la solución dada no es obvia para mí. Pero incluso si de alguna manera logro convencerme de esta solución, sigo sintiendo curiosidad por saber cómo resolver el caso general absoluto (que es mi pregunta)

Alguien me puede explicar una solución paso a paso (que nuevamente en mi opinión debería tomar tiempo logarítmico, es decir, O (log (n ₁ ) + log (n ₂ ) ... + log (n _N ) donde n ₁ , n ₂ .. .n _N son las longitudes de las n matrices) que comienzan desde los casos más específicos y pasan a la más general?

Sé que hay preguntas similares para casos más específicos en Internet, pero no he encontrado una respuesta clara y convincente.

Here hay un enlace a una pregunta (y su respuesta) sobre SO que trata con 5 arreglos ordenados y encuentra la mediana del arreglo combinado. La respuesta se vuelve demasiado complicada para que pueda generalizarla.

Incluso los enfoques limpios para los casos más específicos (como mencioné durante el post) son bienvenidos.

PS: ¿Crees que esto se puede generalizar aún más en el caso de matrices sin clasificar?

PPS: No es un problema de tarea, solo me estoy preparando para las entrevistas.

Answer 1

Encuentre el código C # a continuación para encontrar el k-ésimo elemento más pequeño en la unión de dos matrices ordenadas. Complejidad del tiempo: O (logk)

public int findKthElement(int k, int[] array1, int start1, int end1, int[] array2, int start2, int end2)
{
// if (k>m+n) exception
if (k == 0)
{
return Math.Min(array1[start1], array2[start2]);
}
if (start1 == end1)
{
return array2[k];
}
if (start2 == end2)
{
return array1[k];
}
int mid = k / 2;
int sub1 = Math.Min(mid, end1 - start1);
int sub2 = Math.Min(mid, end2 - start2);
if (array1[start1 + sub1] < array2[start2 + sub2])
{
return findKthElement(k - mid, array1, start1 + sub1, end1, array2, start2, end2);
}
else
{
return findKthElement(k - mid, array1, start1, end1, array2, start2 + sub2, end2);
}
}

Answer 2

Esto no generaliza los enlaces, pero resuelve el problema:

1. Ir a través de todos los arrays y si alguno tiene longitud> k, trunca a la longitud k (esto es una tontería, pero luego nos metemos con k, así que hazlo de todos modos)
2. Identifique la matriz restante más grande A. Si hay más de una, elija una.
3. Elija el elemento medio M de la matriz más grande A.
4. Use una búsqueda binaria en las matrices restantes para encontrar el mismo elemento (o el elemento más grande <= M).
5. Basándose en los índices de los diversos elementos, calcule el número total de elementos <= M y> M. Esto le dará dos números: L, el número <= M y G, el número> M
6. Si k <L, trunca todas las matrices en los puntos de división que ha encontrado e itere en las matrices más pequeñas (use las mitades inferiores).
7. Si k> L, trunca todas las matrices en los puntos de división que ha encontrado e itere en las matrices más pequeñas (use las mitades superiores y busque el elemento (kL).

Cuando llegue al punto donde solo tiene un elemento por matriz (o 0), cree una nueva matriz de tamaño n con esos datos, ordene y elija el elemento kth.

Debido a que siempre se garantiza la eliminación de al menos la mitad de una matriz, en N iteraciones, se eliminará la mitad de los elementos. Eso significa que hay N log k iteraciones. Cada iteración es de orden N log k (debido a las búsquedas binarias), por lo que todo es N ^ 2 (log k) ^ 2 Eso es todo, por supuesto, el peor de los casos, basado en la suposición de que solo se deshace de la mitad de la matriz más grande, no de las otras matrices. En la práctica, me imagino que el rendimiento típico sería bastante mejor que el peor de los casos.

Answer 3

Esto podría considerarse la segunda mitad de una ordenación de fusión. Simplemente podríamos fusionar todas las listas ordenadas en una sola lista ... pero solo mantener los elementos k en las listas combinadas de una combinación a otra. Esto tiene la ventaja de que solo utiliza el espacio O (k), pero algo ligeramente mejor que la complejidad O (n log n) de la combinación de clasificación. Es decir, en la práctica debería funcionar un poco más rápido que una ordenación por fusión. La elección del kth más pequeño de la lista final combinada es O (1). Este tipo de complejidad no es tan malo.

Answer 4

Existe una generalización que resuelve el problema en tiempo O (N log k), vea la pregunta aquí .

Answer 5

No se puede hacer en menos de O(n) tiempo. Bosquejo de prueba Si lo hiciera, tendría que no mirar completamente al menos una matriz. Obviamente, una matriz puede cambiar arbitrariamente el valor del elemento kth .

Tengo un O(n*log(n)*log(m)) relativamente simple donde m es la longitud de la matriz más larga. Estoy seguro de que es posible ser un poco más rápido, pero no mucho más rápido.

Considere el caso simple en el que tiene n matrices cada una de longitud 1. Obviamente, esto es isomorfo para encontrar el elemento k th en una lista no clasificada de longitud n . Es posible encontrar esto en O(n) , consulte el algoritmo Mediana de las medianas, originalmente de Blum, Floyd, Pratt, Rivest y Tarjan , y no son posibles algoritmos (asintóticamente) más rápidos.

Ahora el problema es cómo expandir esto a arreglos ordenados más largos. Aquí está el algoritmo: Encuentra la mediana de cada matriz. Ordene la lista de tuplas (median,length of array/2) y clasifíquela por mediana. Camina manteniendo una suma de las longitudes, hasta que alcances una suma mayor que k. Ahora tienes un par de medianas, de modo que sabes que el elemento kth está entre ellas. Ahora, para cada mediana, sabemos si el kth es mayor o menor que él, por lo que podemos tirar la mitad de cada matriz. Repetir. Una vez que todas las matrices tienen un elemento de longitud (o menos), usamos el algoritmo de selección.

Implementar esto revelará complejidades adicionales y condiciones de borde, pero nada que incremente la complejidad asintótica. Cada paso

1. Encuentra las medianas o las matrices, O(1) cada una, entonces O(n) total
2. Clasifica las medianas O(n log n)
3. Recorre la lista ordenada O(n)
4. Corta las matrices O(1) cada una, O(n) total

es decir O(n) + O(n log n) + O(n) + O(n) = O(n log n) . Y, debemos realizar esto hasta que la matriz más larga sea la longitud 1, que tomará los pasos de log m para un total de O(n*log(n)*log(m))

Pregunta si esto se puede generalizar en el caso de matrices sin clasificar. Lamentablemente, la respuesta es no. Considere el caso donde solo tenemos una matriz, entonces el mejor algoritmo tendrá que comparar al menos una vez con cada elemento para obtener un total de O(m) . Si hubiera una solución más rápida para n matrices sin clasificar, entonces podríamos implementar la selección dividiendo nuestra matriz única en n partes. Como acabamos de probar que la selección es O(m) , estamos atascados.

Answer 6

Puedes ver mi respuesta reciente en la pregunta relacionada here . La misma idea se puede generalizar a varios arreglos en lugar de 2. En cada iteración, puede rechazar la segunda mitad del arreglo con el elemento medio más grande si k es menor que la suma de los índices medios de todos los arreglos. Alternativamente, puede rechazar la primera mitad de la matriz con el elemento central más pequeño si k es mayor que la suma de los índices medios de todas las matrices, ajuste k. Sigue haciendo esto hasta que tengas todos menos una matriz reducida a 0 en longitud. La respuesta es el elemento kth de la última matriz que no se eliminó a 0 elementos.

Análisis en tiempo de ejecución:

Usted se deshace de la mitad de una matriz en cada iteración. Pero para determinar qué matriz se va a reducir, dedica un tiempo lineal al número de matrices. Suponga que cada matriz es de la misma longitud, el tiempo de ejecución será c c log (n), donde c es el número de matrices y n es la longitud de cada matriz.

Answer 7

Si el k no es tan grande, podemos mantener una cola de prioridad mínima. luego haga un bucle para cada cabecera de la matriz ordenada para obtener el elemento más pequeño y poner en cola. cuando el tamaño de la cola es k. obtenemos la primera k mas pequeña.

tal vez podamos considerar la matriz ordenada n como cubos y luego probar el método de clasificación de cubos.