Problema
Ambas listas están ordenadas en orden ascendente. Encuentra la mediana de todos sus números juntos; si la cantidad total es par, es el promedio de los dos valores centrales. Es posible una búsqueda por partición en O(log(m + n)), pero se acepta cualquier método correcto dentro de los límites.
Implementa median_of_two(first, second).
Entrada
first: Una lista ordenada. second: Una lista ordenada.
Salida
Devuelve la mediana.
Restricciones
0 ≤ longitudes ≤ 100,000; la longitud combinada es al menos 1
Ejemplos
Entrada:
first = [1, 3]
second = [2]
Salida esperada:
expected = 2.0Entrada:
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};
Salida esperada:
double expected = 2.0;Entrada:
long[] first = new long[] {1, 3};
long[] second = new long[] {2};
Salida esperada:
double expected = 2.0;Explicación
Combinado: [1, 2, 3]; el valor central es 2.
Entrada:
first = [1, 2]
second = [3, 4]
Salida esperada:
expected = 2.5Entrada:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
Salida esperada:
double expected = 2.5;Entrada:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
Salida esperada:
double expected = 2.5;Explicación
Combinado: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
El orden combinado importa, pero no necesitas fusionarlo todo si puedes encontrar directamente el corte central.
Pista 2
Busca una partición donde las mitades izquierdas contengan exactamente los elementos centrales inferiores y cada valor de la izquierda no sea mayor que cualquiera de la derecha.
Pista 3
Maneja con cuidado los arreglos vacíos y las longitudes totales pares e impares, porque la mediana puede salir de un valor central o de dos.
Complejidad esperada
tiempo O(log(min(m, n))), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.