Dados N enteros arbitrarios, ¿cómo encontrar el promedio de la mitad superior de estos números? ¿Hay una solución de O (n)? Si no, ¿es posible probar que no es posible?¿Cómo encontrar el promedio de la mitad superior de N números?
Primero, encuentre median de la matriz dada (es takes linear time).
Luego, simplemente recorra la matriz y resuma todos los elementos que sean mayores que la mediana.
Cuenta cuántos elementos se suman (M). Si M < N/2, significa que varios elementos que son iguales al valor mediano (es decir, N/2 - M) pertenecen a la mitad superior. Agregue a su suma tantos valores medianos. Necesitamos esta complejidad porque no sabemos cuántos elementos medianos (puede haber varios) pertenecen a la mitad superior: si los tomamos todos, podemos terminar sumando más de N/2 elementos.
Ahora tiene la suma de la mitad superior de la matriz. Divida por N/2, y listo.
O el código podría ser más simple si hace un pase O (n) adicional y solo cuenta el número de elementos igual a la mediana. Eso te dice cuántos elementos iguales a la mediana incluir en el promedio. –
Incluso más simple sería usar que casi cualquier algoritmo para encontrar una mediana también encuentra una partición de la lista de entrada en una mitad superior y una inferior. Por lo tanto, una vez que se encuentra la mediana, todos los elementos en la mitad superior ya son conocidos. – Accipitridae
Yo sugeriría esto:
Uso ordenación rápida, seleccione alguna de pivote. Esto dividirá su lista en dos sublistas, una más pequeña que el pivote, una mayor que esa. Si el tamaño de la sublista más pequeña es < = N/2, calcule el promedio digamos a1.
Si size == N/2 or size == N/2 -1
ha terminado de inmediato.
Si no se reparticiona la sublista mayor hasta que el tamaño total sea N/2.
Si size> N/2 particiona la sublista más pequeña.
Repita todo hasta el final.
P.S: no necesita ordenar.
Es 'O (n^2)' en el peor de los casos ... –
Puede usar una cola de prioridad. Inserte los elementos en la cola manteniendo un recuento de la cantidad de elementos que ha visto, n. Extraiga n/2 elementos máximos de la cola en un acumulador y calcule el promedio.
Con una estructura de datos bien elegido detrás de la cola, como un montón de Fibonacci, esto le dará O(n log n) tiempo de ejecución, como la inserción y la extracción es O(1) es O(log n).
Lamentablemente no el tiempo de ejecución O (n) que estaba buscando, pero con la estructura de datos ya implementada, esto produciría un código sencillo muy comprensible.
* Encontrar * el máximo es O (1) en un montón de Fibonacci, pero * quitándolo * (permitiendo así lo que era el segundo al máximo se encuentra en otro O (1)) es O (log n). Si "insert" y "remove max" realmente fueran ambos O (1) en un montón de Fibonacci, entonces sería posible usar uno para realizar una clasificación de comparación en O (n). –
Tiene toda la razón, disculpas, he editado mi respuesta en consecuencia. ¡Ese nlogn molesto más bajo en la clasificación! –
Esto es obviamente solucionable en tiempo lineal, si puede encontrar la mediana en tiempo lineal. Y encontrar una mediana en el tiempo lineal es complicado, pero posible. Ver por ejemplo el artículo de wikipedia en selection algorithms.
¿Se supone que la pregunta se relaciona con la programación (es decir, resolver esto usando un programa)? – BoltClock
Yo donno. Puedes dar fórmula matemática si tienes método. Es solo una pregunta de entrevista. – Seeker
Esta es una de las preguntas, donde el entrevistador quiere saber si el candidato puede reducir los problemas del mundo real a los algoritmos conocidos. Esto a menudo es más importante que poder recitar los algoritmos en sí. Por lo tanto, me cuesta entender por qué esta pregunta fue cerrada como fuera de tema. – Accipitridae