Squares of a Sorted Array

Q: Qual é a complexidade de tempo dos quadrados de um array ordenado?

A solução com dois ponteiros é executada em tempo O(n) : cada valor é elevado ao quadrado e inserido uma vez. Elevar ao quadrado e depois ordenar custa O(n log n) . Ambas usam O(n) de memória para o resultado.

FácilDois ponteiros Ordenação

+10

Você recebe um array de números inteiros nums ordenado em ordem não decrescente. Ele pode conter valores negativos. Eleve cada valor ao quadrado e retorne os quadrados em um novo array, também ordenado em ordem não decrescente.

Função

sortedSquares(nums: integer-array) → integer-array

numsinteger-array: o array ordenado de números inteiros, com negativos permitidos
Retornainteger-array: o quadrado de cada valor, em ordem não decrescente

Restrições

1 ≤ nums.length ≤ 4000
-10⁴ ≤ nums[i] ≤ 10⁴
nums está ordenado em ordem não decrescente.

Exemplos

Entrada: nums = [-6, -2, 1, 3, 7]
Saída: [1, 4, 9, 36, 49]
Explicação: Os quadrados na ordem original são 36, 4, 1, 9 e 49. Os valores negativos -6 e -2 resultam em quadrados grandes, então a ordenação move 36 para perto do final: [1, 4, 9, 36, 49].

Entrada: nums = [-9, -4, -1]
Saída: [1, 16, 81]
Explicação: Todos os valores são negativos, então os quadrados aparecem em ordem inversa: 81, 16, 1 se torna [1, 16, 81].

+14 testes ocultos ao enviar

Para ir além

Elevar ao quadrado e ordenar leva O(n log n). Você consegue fazer isso em O(n)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Elevar ao quadrado mantém a ordem dos valores não negativos, mas inverte a ordem dos negativos, então os quadrados não ficam ordenados. Ordená-los novamente funciona, mas ignora a ordem recebida. O fato principal: o maior quadrado sempre vem de uma das duas extremidades de nums. Compare as duas extremidades, coloque o maior quadrado no fim do resultado e avance para o meio.

Eleve ao quadrado e, depois, ordene

Intuição

Crie um novo array com o quadrado de cada valor e, depois, ordene-o. Os quadrados nunca são negativos, e a ordenação os coloca em ordem, independentemente de onde vieram.

Para [-6, -2, 1, 3, 7], os quadrados são [36, 4, 1, 9, 49], e a ordenação resulta em [1, 4, 9, 36, 49].

A ordenação custa O(n log n). Isso é rápido o suficiente aqui, mas trata a entrada como se ela não tivesse nenhuma ordem. A próxima abordagem aproveita a ordem e precisa de apenas uma passagem.

Algoritmo

Crie um array com x * x para cada x em nums.
Ordene-o em ordem numérica crescente.
Retorne-o.

def sortedSquares(nums):
    return sorted(x * x for x in nums)

Dois ponteiros, um em cada extremidade

Intuição

Pense nos quadrados como as distâncias em relação a 0, elevadas ao quadrado. Em um array ordenado, os valores mais distantes de 0 ficam nas duas extremidades: o valor mais negativo à esquerda e o mais positivo à direita. Portanto, o maior quadrado é nums[left]² ou nums[right]², nunca qualquer valor entre eles.

Mantenha left em 0 e right em n-1, e preencha o resultado começando pela última posição e seguindo para trás. A cada etapa, compare os quadrados das duas extremidades, escreva o maior na posição atual e mova esse ponteiro para dentro. O que resta entre os ponteiros continua sendo um array ordenado, então o mesmo princípio vale em cada etapa.

Em [-6, -2, 1, 3, 7]: 49 é maior que 36 e vai para a última posição. Depois, 36 é maior que 9, 9 é maior que 4, 4 é maior que 1, e o 1 preenche a posição 0. O resultado é [1, 4, 9, 36, 49]. Cada valor é colocado uma vez: tempo O(n), e o resultado é o único array extra.

Algoritmo

Crie um array de resultados com comprimento n. Defina left como 0 e right como n-1.
Percorra as posições de n-1 até 0 usando pos.
Compare nums[left]² com nums[right]².
Escreva o maior quadrado em pos e mova esse ponteiro um passo para dentro.
Retorne o 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

Armadilhas e casos extremos

A versão com dois ponteiros é curta, mas alguns detalhes podem fazê-la falhar.

Preencher o resultado a partir do início. O menor quadrado fica onde os valores cruzam o 0, o que pode ser em qualquer lugar no meio. As extremidades só indicam o maior quadrado. Preencha de trás para frente.
Comparar nums[left] com nums[right] em vez de comparar seus quadrados ou valores absolutos. -6 é menor que 3, mas seu quadrado é maior.
Parar quando left encontrar right. Quando eles são iguais, ainda há um valor que não foi colocado; percorra todas as posições do resultado ou use left <= right.
Entrada toda negativa ou toda positiva. Com [-9, -4, -1], o ponteiro esquerdo faz todo o trabalho, e com [2, 5, 8], o direito faz. Mesmo assim, ambos devem gerar uma saída ordenada.
Em JavaScript e TypeScript, sort() sem um comparador ordena números como texto, então [1, 4, 36, 9] se torna [1, 36, 4, 9]. Passe (a, b) => a - b.

Perguntas frequentes4

Qual é a complexidade de tempo dos quadrados de um array ordenado?

A solução com dois ponteiros é executada em tempo O(n): cada valor é elevado ao quadrado e inserido uma vez. Elevar ao quadrado e depois ordenar custa O(n log n). Ambas usam O(n) de memória para o resultado.

Por que o maior quadrado vem de uma das duas extremidades?

O quadrado aumenta com a distância de 0. Em um array ordenado, o valor mais distante abaixo de 0 é o primeiro, e o valor mais distante acima de 0 é o último. Todo valor entre eles está mais perto de 0 do que um deles, então seu quadrado não pode ser o maior.

Você pode preencher o resultado começando pelo início?

Sim, mas primeiro você precisa encontrar onde os valores cruzam 0, por exemplo, com uma busca binária. Depois, dois ponteiros avançam para fora a partir desse ponto, como na intercalação de duas listas ordenadas: os valores negativos são lidos da direita para a esquerda, e os não negativos, da esquerda para a direita. Preencher a partir do fim evita a busca, porque as extremidades são conhecidas desde o início.

Squares of a Sorted Array é um problema de intercalação?

Disfarçados, sim. Os valores negativos elevados ao quadrado formam uma lista ordenada (lida da direita para a esquerda), e os valores não negativos elevados ao quadrado formam outra. Combiná-las é a etapa de intercalação do merge sort, e é por isso que isso pode ser feito em uma única passagem linear.

Python

def sortedSquares(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

nums = [-6, -2, 1, 3, 7]

Esperado

[1, 4, 9, 36, 49]