c++ - maltrata - juan de dios pantoja manipula a kimberly
Número(s) perdido(s) Entrevista Pregunta Redux (6)
Debido a que los números se toman de un rango pequeño y finito, se pueden "ordenar" en tiempo lineal.
Todo lo que hacemos es inicializar una matriz de 100 valores booleanos y, para cada entrada, establecer el valor booleano correspondiente a cada número en la entrada, y luego revisar el informe de los valores booleanos no configurados.
El problema común de la entrevista para determinar el valor faltante en un rango de 1 a N se ha hecho miles de veces. Las variaciones incluyen 2 valores faltantes hasta K valores faltantes.
Problema de ejemplo: rango [1,10] (1 2 4 5 7 8 9 10) = {3,6}
Aquí hay un ejemplo de las diversas soluciones:
Mi pregunta es que ver como el caso simple de un valor faltante es de complejidad O (n) y que la complejidad de los casos más grandes converge aproximadamente en algo más grande que O (nlogn):
¿No podría ser más fácil responder la pregunta diciendo ordenar (fusionar) el rango e iterar sobre él observando los elementos que faltan?
Esta solución no debe tomar más de O (nlogn) y es capaz de resolver el problema para rangos distintos de 1 a N, como 10 a 1000 o -100 a +100, etc.
¿Hay alguna razón para creer que las soluciones dadas en el enlace SO anterior serán mejores que la solución basada en clasificación para un mayor número de valores perdidos?
Nota: Parece que muchas de las soluciones comunes a este problema, suponen un enfoque teórico de números únicos. Si se hace una pregunta de este tipo en una entrevista S / E, ¿no sería prudente utilizar un enfoque más algorítmico / informático, suponiendo que el enfoque esté a la par con la complejidad de la solución de la teoría de números ...
Más enlaces relacionados:
Que hay de esto
- Crea tu propio conjunto que contiene todos los números.
- eliminar el conjunto dado de números de su conjunto (no es necesario ordenar)
Lo que queda en tu set son los números que faltan.
Si el rango se le entrega con mucha antelación, en este caso el rango es [1,10], puede realizar una operación XOR con su rango y los números que se le han asignado. Dado que XOR es una operación conmutativa. Te quedarás con {3,6}
(1 2 3 4 5 6 7 8 9 10) XOR (1 2 4 5 7 8 9 10) = {3,6}
Si hay un total de N elementos donde cada número x es tal que 1 <= x <= N, entonces podemos resolver esto en O (nlogn) complejidad de tiempo y O (1) espacio de complejidad.
- Primero ordene la matriz usando quicksort o mergesort.
- Escanee a través de la matriz ordenada y si la diferencia entre el número escaneado anteriormente, ay el número actual, b es igual a 2 (b - a = 2), entonces el número que falta es a + 1. Esto se puede extender a una condición donde (b - a> 2).
La complejidad del tiempo es O (nlogn) + O (n) casi igual a O (nlogn) cuando N> 100.
Si la solución dada es teóricamente mejor que la clasificación, depende de N y K. Si bien su solución tiene una complejidad de O(N*log(N)) , la solución dada es O(N*K) . Creo que la solución dada es (igual que la solución de clasificación) capaz de resolver cualquier rango [A, B] simplemente transformando el rango [A, B] en [1, N] .
Solo está especificando la complejidad del tiempo, pero también es importante tener en cuenta la complejidad del espacio.
La complejidad del problema se puede especificar en términos de N (la longitud del rango) y K (el número de elementos que faltan).
En la pregunta que vinculas, la solución de usar ecuaciones es O (K) en el espacio (¿o quizás un poco más?), Ya que necesitas una ecuación por valor desconocido.
También está el punto de conservación: ¿puede alterar la lista de elementos conocidos? En algunos casos, esto es indeseable, en cuyo caso cualquier solución que implique reordenar los elementos o consumirlos debe hacer primero una copia, O (NK) en el espacio.
No puedo ver más rápido que una solución lineal: necesita leer todos los elementos conocidos (NK) y generar todos los elementos desconocidos (K). Por lo tanto, no puede obtener mejor que O (N) en el tiempo.
Analicemos las soluciones.
- Destrucción, espacio O (N), tiempo O (N log N): clasificación en el lugar
- Conservación, espacio O (K)?, O (N log N) tiempo: sistema de ecuaciones
- Conservación, espacio O (N), tiempo O (N): ordenación de conteo
Personalmente, aunque me parece inteligente la solución del sistema de ecuaciones , probablemente usaría alguna de las soluciones de clasificación. Seamos realistas: son mucho más fáciles de codificar, especialmente el ordenamiento de conteo.
Y en lo que se refiere al tiempo, en una ejecución real, creo que el "ordenamiento de conteo" superaría a todas las demás soluciones sin más.
Nota : la clasificación de conteo no requiere que el rango sea [0, X) , cualquier rango servirá, ya que cualquier rango finito se puede transponer a la forma [0, X) mediante una traducción simple.
EDITAR :
Cambió la clasificación a O (N), uno necesita tener todos los elementos disponibles para ordenarlos.
Después de haber tenido algo de tiempo para pensar en el problema, también tengo otra solución que proponer. Como se señaló, cuando N crece (dramáticamente), el espacio requerido podría explotar. Sin embargo, si K es pequeño, podríamos cambiar nuestra representación de la lista, utilizando intervalos:
-
{4, 5, 3, 1, 7}
puede ser representado como
-
[1,1] U [3,5] U [7,7]
En el caso promedio, mantener una lista ordenada de intervalos es mucho menos costoso que mantener una lista ordenada de elementos, y también es tan fácil deducir los números faltantes.
La complejidad del tiempo es fácil: O (N log N), después de todo, es básicamente una ordenación por inserción.
Por supuesto, lo que es realmente interesante es que no hay necesidad de almacenar la lista, por lo que puede alimentarla con un flujo al algoritmo.
Por otro lado, me resulta bastante difícil averiguar la complejidad media del espacio. El espacio "final" ocupado es O (K) (a lo sumo K + 1 intervalos), pero durante la construcción habrá muchos más intervalos faltantes a medida que introducimos los elementos sin ningún orden en particular.
El peor de los casos es bastante fácil: intervalos N / 2 (piense en números pares frente a pares). Sin embargo, no puedo averiguar el caso promedio. Mi instinto me dice que debería ser mejor que O (N), pero no soy tan confiado.