Quadrados de uma lista ordenada
A missão
Problema
Uma lista de inteiros está ordenada em ordem não decrescente e pode conter valores negativos. Retorne uma nova lista com o quadrado de cada valor, também em ordem não decrescente. Elevar ao quadrado e depois ordenar leva tempo O(n log n); o objetivo é O(n), aproveitando a ordem que a entrada já tem.
Exemplos
Input: nums = [-5, -2, 1, 3, 4]
Output: [1, 4, 9, 16, 25]
Por quê: -5 é o menor valor, mas gera o maior quadrado
Input: nums = [-7, -3, -2]
Output: [4, 9, 49]
Por quê: todos são negativos, então os quadrados saem em ordem inversa
Input: nums = []
Output: []
Por quê: edge case: não há nada para elevar ao quadrado
Dicas
0 / 3
Os quadrados perdem a ordem porque valores muito negativos viram quadrados grandes. De que ponto da entrada pode vir o maior quadrado?
O maior quadrado sempre vem de uma das duas pontas da entrada. Isso sugere dois ponteiros (two pointers) indo para o meio e uma saída preenchida de trás para frente.
Mantenha um ponteiro em cada ponta e uma posição de escrita no último slot da saída. Compare os valores absolutos nos dois ponteiros, escreva o quadrado maior, mova esse ponteiro para dentro e recue a posição de escrita até preencher todos os slots.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- nums is sorted in non-decreasing order
- values may be negative
- target O(n) time
Solução
O maior valor absoluto está sempre em uma das pontas da entrada ordenada, então o maior quadrado ainda não escrito é sempre um dos dois quadrados das pontas. Dois ponteiros começam nas pontas, e a saída é preenchida do último slot para trás, a mesma ideia de trás para frente usada para mesclar dois arrays ordenados. Cada passo escreve um quadrado e move um ponteiro, então o loop roda exatamente n vezes. O tempo é O(n) e o espaço é O(n) para a saída.
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([])) # -> []Travou na ideia, e não no código? Mesclar arrays ordenados explica isso.