Cuadrados de una lista ordenada
La misión
Problema
Una lista de enteros está ordenada de forma no decreciente y puede contener valores negativos. Devuelve una lista nueva con el cuadrado de cada valor, también en orden no decreciente. Elevar al cuadrado y luego ordenar toma tiempo O(n log n); el objetivo es O(n) aprovechando el orden que ya tiene la entrada.
Ejemplos
Input: nums = [-5, -2, 1, 3, 4]
Output: [1, 4, 9, 16, 25]
Por qué: -5 es el valor más pequeño, pero da el cuadrado más grande
Input: nums = [-7, -3, -2]
Output: [4, 9, 49]
Por qué: todos son negativos, así que los cuadrados salen en orden inverso
Input: nums = []
Output: []
Por qué: caso límite: no hay nada que elevar al cuadrado
Pistas
0 / 3
Los cuadrados pierden el orden porque los valores negativos grandes se convierten en cuadrados grandes. ¿De qué parte de la entrada puede salir el cuadrado más grande?
El cuadrado más grande siempre sale de uno de los dos extremos de la entrada. Eso sugiere dos punteros que avanzan hacia adentro y una salida que se llena desde el final.
Mantén un puntero en cada extremo y una posición de escritura en la última casilla de la salida. Compara los valores absolutos en los dos punteros, escribe el cuadrado mayor, mueve ese puntero hacia adentro y retrocede la posición de escritura hasta llenar todas las casillas.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- nums is sorted in non-decreasing order
- values may be negative
- target O(n) time
Solución
El mayor valor absoluto siempre está en un extremo de la entrada ordenada, así que el mayor cuadrado que todavía no se escribió siempre es uno de los dos cuadrados de los extremos. Dos punteros (two pointers) empiezan en los extremos y la salida se llena desde su última casilla hacia atrás, la misma idea de atrás hacia adelante que se usa para fusionar dos arrays (arreglos) ordenados. Cada paso escribe un cuadrado y mueve un puntero, así que el bucle se ejecuta exactamente n veces. El tiempo es O(n) y el espacio es O(n) por la salida.
def sorted_squares(nums):
out = [0] * len(nums)
lo, hi = 0, len(nums) - 1
for write in range(len(nums) - 1, -1, -1): # fill from the back
if abs(nums[lo]) > abs(nums[hi]): # the bigger end gives the bigger square
out[write] = nums[lo] * nums[lo]
lo += 1
else:
out[write] = nums[hi] * nums[hi]
hi -= 1
return out
print(sorted_squares([-5, -2, 1, 3, 4])) # -> [1, 4, 9, 16, 25]
print(sorted_squares([-7, -3, -2])) # -> [4, 9, 49]
print(sorted_squares([])) # -> []¿Lo que te frena es la idea y no el código? Fusionar arrays ordenados lo explica.