Todos los desafíos
Difícil 1 resuelto 100.0% de aceptación

Median of Two Sorted Arrays

Find the median of two sorted lists combined.

Lo que aprenderás

  • Partition two sorted arrays with binary search
  • Find the median in O(log n)
  • Handle even and odd total lengths

Problema

Ver traducción

Both lists are sorted in ascending order. Find the median of all their numbers together; for an even count it is the average of the two middle values. An O(log(m + n)) partition search is possible, but any correct method within the limits is accepted.

Implement median_of_two(first, second).

Input

first: A sorted list. second: A sorted list.

Output

Return the median.

Restricciones

0 ≤ lengths ≤ 100,000; the combined length is at least 1

Ejemplos

Ejemplo 1
Entrada:
first = [1, 3]
second = [2]

Salida esperada:
expected = 2.0
Entrada:
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

Combined: [1, 2, 3]; the middle value is 2.

Ejemplo 2
Entrada:
first = [1, 2]
second = [3, 4]

Salida esperada:
expected = 2.5
Entrada:
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

Combined: [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

The combined order matters, but you do not need to merge everything if you can find the middle split directly.

Pista 2

Search for a partition where left halves contain exactly the lower middle elements and every left value is no larger than every right value.

Pista 3

Handle empty arrays and both odd and even total lengths carefully, since the median may come from one middle value or two.

Complejidad esperada

O(log(min(m, n))) time, O(1) extra space

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 825 ms - 5/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.