Posterior a investigar en diferentes repositorios y sitios de internet al terminar hemos hallado la resolución que te enseñamos a continuación.
Solución:
Puede usar el algoritmo Mediana de medianas para encontrar la mediana de un array en tiempo lineal.
Ya voté a favor de la respuesta de @dasblinkenlight ya que el algoritmo Median of Medians de hecho resuelve este problema en tiempo O(n). Solo quiero agregar que este problema podría resolverse en tiempo O (n) usando montones también. La construcción de un montón se puede hacer en tiempo O(n) usando el método de abajo hacia arriba. Eche un vistazo al siguiente artículo para obtener una explicación detallada Ordenación en montón
Suponiendo que tu array tiene N elementos, debe crear dos montones: un MaxHeap que contiene los primeros N/2 elementos (o (N/2)+1 si N es impar) y un MinHeap que contiene los elementos restantes. Si N es impar, entonces su mediana es el elemento máximo de MaxHeap (O (1) al obtener el máximo). Si N es par, entonces su mediana es (MaxHeap.max()+MinHeap.min())/2 esto también toma O(1). Por lo tanto, el costo real de toda la operación es la operación de creación de montones, que es O(n).
Por cierto, este algoritmo MaxHeap/MinHeap también funciona cuando no conoce el número del array elementos de antemano (si tiene que resolver el mismo problema para una secuencia de enteros, por ejemplo). Puede ver más detalles sobre cómo resolver este problema en el siguiente artículo Median Of integer streams
Quickselect funciona en O(n), esto también se usa en el paso de partición de Quicksort.
Tienes la opción de amparar nuestro trabajo añadiendo un comentario y dejando una puntuación te damos la bienvenida.