Median of Two Sorted Arrays
Recibes dos listas de enteros, nums1 y nums2, cada una ordenada de menor a mayor y con al menos un valor. Devuelve la mediana de todos sus valores juntos, como texto.
Si la cantidad total es impar, la mediana es el valor central, como "4". Si es par, es el promedio de los dos valores centrales, como "2.5" o "-0.5". Escribe un número entero sin punto decimal, y el cero como "0", nunca como "-0". Intenta lograr un tiempo de O(log(min(m, n))).
Función
- nums1integer-array
- la primera lista, ordenada de menor a mayor
- nums2integer-array
- la segunda lista, ordenada de menor a mayor
- Devuelvestring
- la mediana de todos los valores, como texto, por ejemplo, «4» o «-2.5»
Restricciones
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- Ambas listas están ordenadas en orden no decreciente, y los valores pueden repetirse.
Ejemplos
- Entrada
- nums1 = [1, 4]nums2 = [2, 7, 9]
- Salida
- "4"
- Explicación
- En conjunto, los valores son 1, 2, 4, 7, 9. Cinco valores tienen un valor central, el tercero, que es 4.
- Entrada
- nums1 = [1, 2]nums2 = [3, 4]
- Salida
- "2.5"
- Explicación
- En conjunto, los valores son 1, 2, 3, 4. Los dos valores centrales son 2 y 3, su suma es 5 y la mitad de 5 es 2.5.
- Entrada
- nums1 = [-7, -3]nums2 = [-2, 0]
- Salida
- "-2.5"
- Explicación
- En conjunto, los valores son -7, -3, -2, 0. Los valores centrales -3 y -2 suman -5, y la mitad de -5 es -2.5.
Para ir más allá
¿Puedes usar el mismo corte para encontrar el k-ésimo valor más pequeño de las dos listas, para cualquier k, en tiempo logarítmico?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Fusionar las dos listas permite encontrar la mediana en
O(m + n). Para hacerlo mejor, piensa en la mediana como un corte: una línea que divide losm + nvalores en una mitad inferior y una mitad superior del mismo tamaño.La mitad inferior es un prefijo de
nums1más un prefijo denums2. Si tomaivalores denums1, la cantidad denums2se deduce. El corte es correcto cuando el último valor tomado de cada lista no es mayor que el primer valor que queda en la otra.Búsqueda binaria sobre
ien la lista más corta. Si el último valor tomado denums1es demasiado grande, toma menos de esa lista; si el último valor tomado denums2es demasiado grande, toma más. En el corte correcto, la mediana proviene del mayor valor por debajo del corte y del menor por encima de este. Suma esos dos enteros y divide la suma entre dos tú mismo.
Solución
Al combinar las listas se obtiene la mediana en O(m + n), pero la mayoría de los valores que se leen no pueden cambiar la respuesta. La mediana depende únicamente de dónde cae el corte entre la mitad inferior y la superior, y un número determina ese corte: cuántos valores toma la mitad inferior de la lista más corta. La búsqueda binaria lo encuentra en O(log(min(m, n))) pasos.
Combina las dos listas
Intuición
Combina las listas como lo hace el ordenamiento por mezcla, en una sola lista ordenada merged. Con total = m + n, suma merged[(total-1)/2] y merged[total/2], usando división entera. Si el total es impar, ambos son el valor del medio; si es par, son los dos valores del medio, así que la mitad de la suma es la mediana en ambos casos.
Aunque te detengas en el medio, los pasos de la mezcla recorren más de la mitad de los valores, por lo que el tiempo es O(m + n).
Algoritmo
- Fusiona las listas en
merged, tomando siempre el menor valor actual y después el resto de la lista que queda. - Con
total = m + n, sumamerged[(total-1)/2]ymerged[total/2]. - Devuelve la mitad de la suma como texto: divide entre 2 una suma par; para una suma impar, escribe el signo, la mitad del valor absoluto y
.5.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Merge the two sorted lists into one, the way merge sort does.
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
merged.extend(nums1[i:])
merged.extend(nums2[j:])
total = len(merged)
# For an odd total both indexes point at the one middle value.
return half_text(merged[(total - 1) // 2] + merged[total // 2])Búsqueda binaria en el corte
Intuición
Haz que la mitad inferior contenga half = (m+n+1)/2 valores, uno más cuando el total sea impar. Toma i valores del principio de nums1 y j = half-i del principio de nums2. El corte es correcto cuando nada de lo que queda abajo es mayor que nada de lo que queda arriba. Cada lista está ordenada, así que solo quedan dos comprobaciones: left1 ≤ right2 y left2 ≤ right1, donde left es el último valor que una lista aporta a la mitad inferior y right el primero que conserva. Si falta un lado, se considera menos o más infinito.
Si left1 > right2, i es demasiado grande; si left2 > right1, es demasiado pequeño. Así que i se busca mediante búsqueda binaria entre 0 y m. En [1, 2] y [3, 4], i = 1 falla porque left2 = 3 > right1 = 2, y i = 2 funciona: (2 + 3) / 2 = 2.5.
Algoritmo
- Haz que
nums1sea la lista más corta; establecehalf = (m+n+1)/2. - Haz una búsqueda binaria de
idesdelo = 0hastahi = m, conj = half-i. - Lee
left1 = nums1[i-1],right1 = nums1[i],left2 = nums2[j-1]yright2 = nums2[j], usando infinito más allá de un extremo. - Si
left1 > right2, establecehi = i-1. Sileft2 > right1, establecelo = i+1. - En caso contrario, si el total es impar, devuelve
max(left1, left2). Si el total es par, divide entre dosmax(left1, left2) + min(right1, right2)como texto.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Binary search over the shorter list.
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2 # size of the left half; it gets the extra value when m + n is odd
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # values the left half takes from nums1
j = half - i # values it takes from nums2
# An empty side counts as minus or plus infinity.
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 > right2:
hi = i - 1 # too many values from nums1
elif left2 > right1:
lo = i + 1 # too few values from nums1
else:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return str(left_max)
return half_text(left_max + min(right1, right2))
return "" # not reached: sorted input always has a valid split
Errores comunes y casos límite
- Dividir por la mitad usando punto flotante. Python muestra una mediana entera como
3.0, y%fde C muestra 2.5 como2.500000. Mantén la suma como un entero. - Escribir el cociente entero y
.5para una suma impar negativa.-1 / 2es 0 en C y Java, lo que da 0.5 para -0.5;-5 // 2es -3 en Python, lo que da -3.5 para -2.5. Divide el valor absoluto por la mitad y vuelve a poner el signo. - Escribir
-0. Los valores centrales -1 y 1 suman 0, y la respuesta es"0". Toma el signo de la suma. - Buscar en la lista más larga.
j = half-ipuede ser menor que 0 o superarn. Intercambia primero las listas. - Leer
nums1[i-1]cuandoi = 0, como en[9]y[1, 2]. Usa infinitos para los valores que faltan.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de Median of Two Sorted Arrays?
La búsqueda binaria en el corte tarda O(log(min(m, n))) y usa O(1) de espacio, porque cada paso reduce a la mitad los cortes posibles en la lista más corta. La combinación tarda O(m + n): para dos listas de 3000 elementos, unos 12 pasos frente a 6000.
¿Por qué realizar la búsqueda binaria en el arreglo más corto?
Como j = half-i. Como i recorre la lista más corta, j se mantiene entre 0 y la longitud de la lista más larga, así que cada lectura está dentro del rango o más allá de un extremo que tratas como infinito.
¿Cómo se devuelve la mediana sin usar coma flotante?
Suma los dos valores centrales como enteros. Divide entre 2 una suma par. Para una suma impar, escribe la mitad de su valor absoluto y .5, con un signo menos cuando la suma sea negativa: -1 se convierte en "-0.5".
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def findMedianSortedArrays(nums1, nums2):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
nums1 = [1, 4] nums2 = [2, 7, 9]
Salida Esperada
"4"