Así, ha de n matrices ordenadas (no necesariamente de la misma longitud), y va a devolver el k-ésimo elemento más pequeño en el combinado de la matriz (i.e el combinado de la matriz formada por la fusión de todas las n matrices ordenadas)

He estado tratando de ésta y sus otras variantes durante bastante tiempo ahora, y hasta ahora sólo me siento cómodo en el caso de que hay dos matrices de igual longitud, ambos ordenados y uno tiene que volver a la mediana de estos dos.
Esto tiene un tiempo logarítmico complejidad.

Después de esto he intentado generalizar a encontrar k-ésimo más pequeño entre dos matrices ordenadas. Aquí es la pregunta ASÍ.
Incluso en este caso la solución dada no es obvio para mí. Pero, aun si se las arreglan para convencer a mí mismo de esta solución, aún soy curioso en cuanto a cómo resolver la absoluta caso general (que es mi pregunta)

Puede que alguien me explique paso a paso la solución (que de nuevo, en mi opinión, debería tomar un tiempo logarítmico yo.e O( log(n1) + log(n2) … + log(nN), donde n1 n2…nN son las longitudes de las matrices de n), que empieza desde el más específico de los casos y se mueve en el más general?

Sé que preguntas similares para obtener más son los casos específicos que hay en todo el internet, pero no he encontrado una respuesta clara y convincente.

Aquí es un enlace a una pregunta (y su respuesta) sobre LO que trata con 5 matrices ordenadas y la búsqueda de la mediana de la combinación de la matriz. La respuesta sólo se pone demasiado complicado para mí para poder generalizar es.

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

PS: ¿crees que esto puede ser aún más generalizado para el caso de sin clasificar matrices?

PPS: no Es una tarea problema, me acaba de prepararse para las entrevistas.

  • Esta pregunta es más adecuado para el StackProgramming, creo. Yo no puedo responder a su pregunta de todos modos 🙂
  • ¿Qué entiende usted por un tiempo logarítmico? Tenemos dos parámetros n y k. No creo que usted puede conseguir más rápido que O(n) porque usted tendrá que buscar en cada matriz al menos una vez.
  • logarítmica significa algo así como O( lg(n1) + lg(n2) + lg(n3)…) donde n1, n2, n3.. son las longitudes de las matrices de n1, n2, n3…n
InformationsquelleAutor Sushant | 2012-01-06

7 Comentarios

  1. 12

    Esto no generalizar los enlaces, pero no resolver el problema:

    1. Ir a través de todas las matrices y si tienen la longitud > k, truncar a la longitud de la k (este es tonto, pero vamos a trabajar con k más tarde, por lo que hacerlo de todos modos)
    2. Identificar el mayor remanente de la matriz A. Si a más de uno, elegir uno.
    3. Elegir el medio elemento M de la más grande de la matriz A.
    4. Utilizar una búsqueda binaria en el resto de las matrices para encontrar el mismo elemento (o el mayor elemento <= M).
    5. Basado en los índices de los distintos elementos, calcular el número total de elementos <= M y > M. Esto debe darle dos números: L, el número de <= M y G, el número de > M
    6. Si k < L, truncar todas las matrices en los puntos de división se ha encontrado y recorrer en el menor matrices (uso de las mitades inferiores).
    7. Si k > L, truncar todas las matrices en los puntos de división se ha encontrado y recorrer en el menor matrices (uso de las mitades superiores, y la búsqueda de elemento (k-L).

    Cuando llegue al punto donde usted sólo tiene un elemento por matriz (o 0), hacer una nueva matriz de tamaño n con los datos, ordenar y recoger el k-ésimo elemento.

    Porque siempre estás garantiza la eliminación de al menos la mitad de una matriz, en N iteraciones, usted va a deshacerse de la mitad de los elementos. Eso significa que hay N log k iteraciones. Cada iteración es de orden N log k (debido a que el binario de búsqueda), así que todo está N^2 (log k)^2 Eso es todo, por supuesto, el peor de los casos, basada en la suposición de que sólo deshacerse 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 un poco mejor que el peor de los casos.

    • Aseado. Gracias…
    • No piensa usted que puede ser resuelto en N^2LogN por simple min montón. Tomar un montón de tamaño N y poner el mínimo de los elementos de N matrices a continuación, el pop en uno y de verificación de la matriz. Insertar el siguiente elemento de la misma matriz. Seguir haciendo esto salga de una vez tienes que k-ésimo elemento de la pila.
    • geeksforgeeks.org/… Esta solución demuestra que se puede hacer en O(N + kLogN) tiempo.
    • Me corrija si estoy equivocado. Pero yo estaba tan confundido en esta línea That means there are N log k iterations. Para explicar que ni a mí ni a nadie que se confunde como lo hice yo, es porque usted deshacerse de la mitad de los elementos (que es N*K) en cada una de las N iteraciones, por lo que para bajar a los N elementos (ya sea 1 o 0 elemento por matriz), usted necesita log((N * K) / N) = log(K) veces => en total se N * log(K)
  2. 2

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

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

    Considerar el caso simple donde tienes n matrices de cada uno de longitud 1. Obviamente, este es isomorfo a encontrar el késimo elemento en una lista sin ordenar de longitud n. Es posible encontrar esta en O(n), ver La mediana de las Medianas algoritmo, originalmente por Blum, Floyd, Pratt, Rivest y Tarjan, y no (asintóticamente) más rápido algoritmos son posibles.

    Ahora el problema es cómo expandir esto a más matrices ordenadas. Aquí es el algoritmo: Encontrar la mediana de cada matriz. Ordenar la lista de tuplas (median,length of array/2) y ordenar por la mediana. Caminar a través de mantener una suma de las longitudes, hasta llegar a una suma mayor que k. Ahora tiene un par de las medianas, de tal manera que usted sabe el k-ésimo elemento es entre ellos. Ahora para cada mediana, sabemos que si el k-ésimo es mayor o menor que ella, así que podemos tirar la mitad de cada matriz. Repita. Una vez que las matrices son todos de un mismo elemento tiempo (o menos), utilizamos el algoritmo de selección.

    La implementación de este revelará complejidades adicionales y las condiciones de borde, pero nada de lo que aumenta la complejidad asintótica. Cada paso

    1. Encuentra las medianas o las matrices, O(1) cada uno, así que O(n) total
    2. Ordena los camellones O(n log n)
    3. Camina a través de la lista ordenada O(n)
    4. Rodajas de las matrices O(1) cada uno y así, O(n) total

    que es O(n) + O(n log n) + O(n) + O(n) = O(n log n). Y, debemos realizar este hasta la más larga de la matriz es de longitud 1, que se llevará a log m pasos para un total de O(n*log(n)*log(m))


    Se pregunta si esto se puede generalizar para el caso de sin clasificar matrices. Tristemente, la respuesta es no. Considere el caso donde sólo tenemos una matriz, entonces la mejor algoritmo tendrá que comparar al menos una vez con cada elemento para un total de O(m). Si hay una solución más rápida para n sin ordenar matrices, entonces se podría implementar de selección por la división de nuestra matriz en n partes. Ya nos demostró que la selección es O(m), estamos estancados.

    • Este es sólo un caso específico donde k = n/2 i.e encontrar la mediana es equivalente a encontrar el n/2º más pequeño en general. Este particular problema puede ser resuelto por la búsqueda de las medianas de cada matriz (que es O(1) debido a que las matrices están ordenados. Entonces, encontrar el min y el max de estos n medianas O(n) tiempo. Ahora el combinado de la mediana se encuentran entre el min y max de la mediana, por lo que podemos deshacernos de otros elementos. Esta es, esencialmente, O(log(maxM)), pero no estoy seguro. En su caso, la clasificación de las medianas es traer a la complejidad un poco cuando todo lo que necesitamos sería un min y max. +1 por el esfuerzo a pesar de las
    • Yah, que va desde la búsqueda de la mediana a la búsqueda de la kth no es difícil. El problema con sólo escoger el min y el max es que no tiene límites en cómo muchos de los valores que son tirar, a menos que me estoy perdiendo algo. La clasificación de paso le permite tirar de la mitad de los valores. Aún así, sería bueno para bajar a O(n*log m)
    • Tenga en cuenta que mi solución tiene el mismo comportamiento asintótico como el vinculado. Ya que en ese caso n = 5 era tratada como una constante para el big-Oh cálculo.
    • Con el conocimiento de que la mediana es de bw min y max, que sin duda puede tirar la mitad inferior de la matriz correspondiente a la min mediana, medio y superior para el máximo mediana.
    • Y ¿cómo puede este esquema se puede ampliar fácilmente para encontrar kth?
  3. 1

    Usted podría mirar en mi reciente respuesta en la pregunta relacionada con la aquí. La misma idea se puede generalizar a múltiples matrices en lugar de 2. En cada iteración se podría rechazar la segunda mitad de la matriz con los medios más grandes elemento, si k es menor que la suma de mediados de los índices de todas las matrices. Alternativamente, usted podría rechazar la primera mitad de la matriz con la menor media de elemento, si k es mayor que la suma de mediados de los índices de todas las matrices, ajuste k. Siga haciendo esto hasta que tenga todos pero una matriz reducida a 0 en longitud. La respuesta es k-ésimo elemento de la última matriz que no era despojado a 0 elementos.

    Análisis de tiempo de ejecución:

    Deshacerse de la mitad de una matriz en cada iteración. Pero para determinar array que va a ser reducido, de pasar el tiempo lineal con el número de matrices. Asumir que cada matriz es de la misma longitud, el tiempo de ejecución va a ser cclog(n), donde c es el número de matrices y n es la longitud de cada matriz.

  4. 0

    Si el k no es enorme, se puede mantener una prioridad min de cola. luego de bucle por cada cabeza de la matriz ordenada para obtener el elemento más pequeño y es-cola. cuando el tamaño de la cola es k. tenemos la primera k más pequeño .

    tal vez podemos considerar el n matriz ordenada como cubos, a continuación, pruebe el cubo método de ordenación.

    • ¿Qué es la complejidad? Además de la utilización de O(k) el espacio, que va a hacer al menos K pone en cola, que es O(k log(k)). Así que, sí, si K es enorme, tenemos un problema. Estoy de acuerdo en que podría ser una buena solución cuando se necesita todo el k más pequeño de los números, pero en este caso solo tengo el k-ésimo más pequeño.
  5. 0

    Esto podría ser considerado como el segundo medio de una combinación de ordenación. Simplemente se podría combinar todas las listas ordenadas en una sola lista…pero sólo mantener a los k elementos en las listas combinadas de mezcla para combinar. Esto tiene la ventaja de utilizar sólo O(k) el espacio, pero algo un poco mejor que la combinación de tipo de O(n log n) la complejidad. Es decir, se debe en la práctica operan ligeramente más rápido que una combinación de ordenación. La elección de la k-ésimo más pequeño desde el final de la lista combinada es O(1). Esta es la clase de complejidad no es tan malo.

    • Sí, este es uno de los triviales soluciones para el problema, por desgracia no es óptima suficiente.
  6. -1

    Por favor, encontrar el siguiente código en C# para Encontrar el k-ésimo Elemento más pequeño en la Unión de Dos Matrices Ordenadas. El tiempo de Complejidad : 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);
            }
        }
    

Dejar respuesta

Please enter your comment!
Please enter your name here