Merge Sorted Array
Recibes dos arreglos de enteros, nums1 y nums2. Cada uno ya está ordenado en orden no decreciente. Devuelve un solo arreglo que contenga todos los valores de ambos, también en orden no decreciente. Un valor que aparece en ambos arreglos aparece en el resultado tantas veces como aparece en total.
Función
- nums1integer-array
- el primer arreglo ordenado
- nums2integer-array
- el segundo arreglo ordenado
- Devuelveinteger-array
- todos los valores de ambos arreglos en un solo arreglo ordenado, de longitud nums1.length + nums2.length
Restricciones
1 ≤ nums1.length, nums2.length ≤ 2000-105 ≤ nums1[i], nums2[j] ≤ 105nums1ynums2están ordenadas en orden no decreciente.
Ejemplos
- Entrada
- nums1 = [1, 4, 9]nums2 = [2, 3, 10]
- Salida
- [1, 2, 3, 4, 9, 10]
- Explicación
- Lee los dos primeros elementos y conserva el menor: 1, después 2 y 3 de
nums2, después 4 y 9 denums1, y 10 al final. El resultado contiene los seis valores.
- Entrada
- nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
- Salida
- [-5, 0, 0, 0, 6, 8]
- Explicación
- El 0 aparece dos veces en
nums1y una vez ennums2, así que el resultado tiene tres 0. El -5 es menor que todos los elementos denums2y va primero.
- Entrada
- nums1 = [7]nums2 = [3]
- Salida
- [3, 7]
- Explicación
- Cada arreglo contiene un valor. 3 es menor que 7, así que va primero.
+13 pruebas ocultas al enviar
Para ir más allá
¿Puedes combinar k arreglos ordenados, que contienen N valores en total, en tiempo O(N log k)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Ambos arreglos ya están ordenados. ¿Dónde se puede encontrar el valor más pequeño de todo el resultado?
El valor más pequeño que queda siempre está al principio de
nums1o al principio denums2. Mantén un índice por arreglo para indicar dónde está el principio de cada uno.Compara los dos elementos al principio, añade el menor y avanza ese índice. Cuando se agoten los elementos de un arreglo, el resto del otro ya estará ordenado, así que añádelo tal cual.
Solución
Unir los arreglos y ordenarlos da la respuesta correcta, pero descarta el hecho de que ambas mitades ya están ordenadas. El menor valor que queda en total siempre está al principio de uno de los dos arreglos. Mantén un índice por arreglo, toma el menor valor del principio en cada paso y una sola pasada construye el resultado. Este es el paso de fusión de la ordenación por mezcla.
Concatenar y ordenar
Intuición
Coloca todos los valores de nums1 y todos los valores de nums2 en un solo arreglo y, después, ordénalo. El resultado contiene los valores correctos, cada uno tantas veces como aparecía, en el orden correcto.
Para [1, 4, 9] y [2, 3, 10], el arreglo combinado es [1, 4, 9, 2, 3, 10], y al ordenarlo se obtiene [1, 2, 3, 4, 9, 10].
Con m valores en nums1 y n en nums2, una ordenación general cuesta O((m + n) log(m + n)). Funciona y es lo bastante rápida para estos límites, pero no aprovecha el orden ya ordenado que te dieron. El siguiente enfoque sí lo hace y elimina el factor logarítmico.
Algoritmo
- Crea un array con los valores de
nums1seguidos por los denums2. - Ordénalo en orden numérico ascendente.
- Devuélvelo.
def merge(nums1, nums2):
return sorted(nums1 + nums2)Dos punteros, uno por matriz
Intuición
Mantén un índice i en nums1 y j en nums2, ambos empezando en 0. Todo lo que está antes de i y antes de j ya está en el resultado. El menor valor que aún no se ha usado es nums1[i] o nums2[j], porque cada arreglo está ordenado y sus valores restantes solo pueden ser mayores. Añade el menor y avanza ese índice.
Con [1, 4, 9] y [2, 3, 10]: 1 le gana a 2, después 2 le gana a 4, 3 le gana a 4, 4 le gana a 10, 9 le gana a 10. Ahora nums1 se ha agotado, así que el resto de nums2, que es [10], se copia tal cual. El resultado es [1, 2, 3, 4, 9, 10].
Cada paso escribe un valor, así que el bucle se ejecuta m + n veces: tiempo O(m + n). El arreglo de resultados es la única memoria adicional.
Algoritmo
- Establece
iyjen 0 y crea un resultado vacío. - Mientras queden valores en ambos arreglos, compara
nums1[i]connums2[j]. - Añade el menor y avanza su índice. En caso de empate, toma
nums1[i]. - Cuando se agote uno de los arreglos, añade lo que quede del otro.
- Devuelve el resultado.
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# one array is used up; the rest of the other is already sorted
result.extend(nums1[i:])
result.extend(nums2[j:])
return result
Errores comunes y casos límite
La mayoría de los errores aparecen cuando se agota un arreglo o al comparar valores.
- Detener el bucle en cuanto se agota un arreglo y olvidar el resto del otro. Con
[1, 2, 3]y[4, 5, 6], el bucle termina después de 1, 2 y 3, y todavía hay que copiar 4, 5 y 6. - Leer
nums1[i]después de queihaya llegado al final. Comprueba ambos índices antes de comparar. - Eliminar duplicados.
[0, 0]y[0]se combinan en[0, 0, 0], no en[0]. - En JavaScript y TypeScript,
sort()sin comparador ordena los números como texto, así que[-5, 10, 9]se ordena como[-5, 10, 9]. Pasa(a, b) => a - b. - En Lua y R, los arreglos empiezan en 1, así que ambos índices empiezan en 1 y los límites usan
<=.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de combinar dos arreglos ordenados?
Con dos punteros, es O(m + n), donde m y n son las dos longitudes. En cada paso se coloca un valor y ningún valor se examina dos veces. En cambio, concatenar y ordenar cuesta O((m + n) log(m + n)).
¿Cómo combinas dos arreglos ordenados in situ?
Cuando el primer arreglo tiene espacio al final para ambos, llénalo desde atrás. Compara los valores restantes más grandes de los dos arreglos, escribe el mayor en el último espacio libre y avanza hacia la izquierda. Escribir desde atrás nunca sobrescribe un valor del primer arreglo que aún no se haya colocado, así que no se necesita un segundo arreglo.
¿Es combinar dos arreglos ordenados lo mismo que el paso de combinación de merge sort?
Sí. La ordenación por mezcla divide un arreglo en mitades, ordena cada mitad y después une las dos mitades ordenadas con exactamente este bucle de dos punteros. Tomar el valor de la izquierda en caso de empate mantiene los valores iguales en su orden original, lo que hace que la ordenación por mezcla sea estable.
¿Por qué no concatenar los arreglos y llamar a sort?
Da la respuesta correcta y, en la práctica, suele ser rápido. Pero ignora que las entradas ya están ordenadas y cuesta un factor adicional de log. En una entrevista, se espera que uses la fusión con dos punteros, porque demuestra que sabes aprovechar el orden que te dieron.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def merge(nums1, nums2):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums1 = [1, 4, 9] nums2 = [2, 3, 10]
Esperado
[1, 2, 3, 4, 9, 10]