Squares of a Sorted Array
Recibes un arreglo de enteros nums ordenado en orden no decreciente. Puede contener valores negativos. Eleva al cuadrado cada valor y devuelve los cuadrados en un nuevo arreglo, también ordenado en orden no decreciente.
Función
- numsinteger-array
- el arreglo ordenado de números enteros; se permiten los negativos
- Devuelveinteger-array
- el cuadrado de cada valor, ordenados en orden no decreciente
Restricciones
1 ≤ nums.length ≤ 4000-104 ≤ nums[i] ≤ 104numsestá ordenado en orden no decreciente.
Ejemplos
- Entrada
- nums = [-6, -2, 1, 3, 7]
- Salida
- [1, 4, 9, 36, 49]
- Explicación
- Los cuadrados en el orden original son 36, 4, 1, 9 y 49. Los valores negativos -6 y -2 dan cuadrados grandes, así que al ordenar 36 queda cerca del final:
[1, 4, 9, 36, 49].
- Entrada
- nums = [-9, -4, -1]
- Salida
- [1, 16, 81]
- Explicación
- Todos los valores son negativos, así que los cuadrados aparecen en orden inverso: 81, 16, 1 se convierte en
[1, 16, 81].
+14 pruebas ocultas al enviar
Para ir más allá
Elevar al cuadrado y ordenar toma O(n log n). ¿Puedes hacerlo en O(n)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Eleva al cuadrado
[-6, -2, 1, 3, 7]a mano. ¿Qué parte de la matriz pierde su orden y por qué?El cuadrado más grande siempre proviene del primer valor o del último valor de
nums, porque esos dos son los que están más lejos de 0.Coloca un puntero en cada extremo. Compara los dos cuadrados, escribe el más grande al final del resultado y mueve ese puntero hacia dentro. Repite hasta que todas las posiciones estén ocupadas.
Solución
Elevar al cuadrado mantiene el orden de los valores no negativos, pero invierte el de los negativos, así que los cuadrados no quedan ordenados. Ordenarlos de nuevo funciona, pero ignora el orden en que los recibiste. El dato clave: el cuadrado más grande siempre proviene de uno de los dos extremos de nums. Compara los dos extremos, coloca el cuadrado más grande al final del resultado y avanza hacia el centro.
Elevar al cuadrado y luego ordenar
Intuición
Crea un array nuevo con el cuadrado de cada valor y después ordénalo. Los cuadrados nunca son negativos, y al ordenar quedan en orden sin importar de dónde provengan.
Para [-6, -2, 1, 3, 7], los cuadrados son [36, 4, 1, 9, 49], y al ordenarlos se obtiene [1, 4, 9, 36, 49].
La ordenación cuesta O(n log n). Aquí es lo bastante rápida, pero trata la entrada como si no tuviera ningún orden. El siguiente enfoque aprovecha el orden y requiere una sola pasada.
Algoritmo
- Crea un array con
x * xpara cadaxennums. - Ordénalo en orden numérico ascendente.
- Devuélvelo.
def sortedSquares(nums):
return sorted(x * x for x in nums)Dos punteros desde ambos extremos
Intuición
Piensa en los cuadrados como la distancia a 0, elevada al cuadrado. En un array ordenado, los valores más alejados de 0 están en los dos extremos: el valor más negativo a la izquierda y el más positivo a la derecha. Así que el cuadrado más grande es nums[left]² o nums[right]², nunca uno que esté entre ellos.
Mantén left en 0 y right en n-1, y llena el resultado empezando por su última posición y avanzando hacia atrás. En cada paso, compara los cuadrados de los dos extremos, escribe el mayor en la posición actual y mueve ese puntero hacia el centro. Lo que queda entre los punteros sigue siendo un array ordenado, así que el mismo principio se cumple en cada paso.
En [-6, -2, 1, 3, 7]: 49 supera a 36 y va al final. Después, 36 supera a 9, 9 supera a 4, 4 supera a 1, y el 1 ocupa la posición 0. El resultado es [1, 4, 9, 36, 49]. Cada valor se coloca una vez: tiempo O(n), y el resultado es el único array adicional.
Algoritmo
- Crea un arreglo de resultados de longitud
n. Estableceleften 0 yrightenn-1. - Recorre la posición
posdesden-1hasta 0. - Compara
nums[left]²connums[right]². - Escribe el cuadrado mayor en
posy mueve ese puntero un paso hacia adentro. - Devuelve el resultado.
def sortedSquares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
# the largest square left is always at one of the two ends
for pos in range(n - 1, -1, -1):
left_sq = nums[left] * nums[left]
right_sq = nums[right] * nums[right]
if left_sq > right_sq:
result[pos] = left_sq
left += 1
else:
result[pos] = right_sq
right -= 1
return result
Errores comunes y casos límite
La versión con dos punteros es corta, pero algunos detalles hacen que falle.
- Llenar el resultado desde el principio. El cuadrado más pequeño se encuentra donde los valores cruzan el 0, que puede estar en cualquier punto intermedio. Los extremos solo indican el cuadrado más grande. Llénalo desde el final.
- Comparar
nums[left]connums[right]en lugar de comparar sus cuadrados o sus valores absolutos. -6 es menor que 3, pero su cuadrado es mayor. - Detenerse cuando
leftalcanza aright. Cuando son iguales, todavía queda un valor sin colocar; recorre todas las posiciones del resultado o usaleft <= right. - Entrada totalmente negativa o totalmente positiva. Con
[-9, -4, -1], el puntero izquierdo hace todo el trabajo, y con[2, 5, 8], lo hace el derecho. En ambos casos, el resultado debe seguir estando ordenado. - En JavaScript y TypeScript,
sort()sin comparador ordena los números como texto, así que[1, 4, 36, 9]se convierte en[1, 36, 4, 9]. Pasa(a, b) => a - b.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de Cuadrados de un array ordenado?
La solución de dos punteros se ejecuta en tiempo O(n): cada valor se eleva al cuadrado y se coloca una vez. Elevar al cuadrado y después ordenar cuesta O(n log n). Ambas usan O(n) de memoria para el resultado.
¿Por qué el cuadrado más grande se obtiene de uno de los dos extremos?
Un cuadrado aumenta con la distancia desde 0. En un arreglo ordenado, el valor más alejado por debajo de 0 es el primero, y el valor más alejado por encima de 0 es el último. Todos los valores intermedios están más cerca de 0 que uno de ellos, así que su cuadrado no puede ser el mayor.
¿Puedes completar el resultado desde el principio?
Sí, pero primero tienes que encontrar dónde los valores cruzan el 0, por ejemplo, mediante una búsqueda binaria. Después, dos punteros avanzan hacia afuera desde ese punto, como al combinar dos listas ordenadas: los negativos se leen de derecha a izquierda y los no negativos, de izquierda a derecha. Rellenar desde el final evita la búsqueda, porque los extremos se conocen desde el principio.
¿Es Cuadrados de un array ordenado un problema de fusión?
De forma encubierta, sí. Los valores negativos elevados al cuadrado forman una lista ordenada (leída de derecha a izquierda), y los valores no negativos elevados al cuadrado forman otra. Combinarlas es el paso de fusión de la ordenación por fusión, por eso se puede hacer en una sola pasada lineal.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def sortedSquares(nums):
# Escribe el código aquíCaso 1
Caso 2
Entrada
nums = [-6, -2, 1, 3, 7]
Esperado
[1, 4, 9, 36, 49]