Pular para o conteúdo

Quadrados de uma lista ordenada

Fácil#two-pointers#merge-from-back~15 min

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

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

Travou na ideia, e não no código? Mesclar arrays ordenados explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado