Move Zeroes

Q: Como mover os zeros para o final sem alterar a ordem dos outros elementos?

Mantenha um índice write para a próxima posição livre no início e percorra com um segundo índice. Cada valor diferente de zero que você encontrar é trocado para a posição write , e write avança uma posição para a direita. Os valores são colocados na ordem em que você os encontra, então a ordem relativa deles nunca muda.

FácilDois ponteiros

+10

Você recebe um array de inteiros nums. Mova todos os 0 para o final do array e mantenha os outros valores na ordem em que estavam. Retorne o array reorganizado, que tem o mesmo tamanho que nums.

Função

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

numsinteger-array: o array de números inteiros a ser reorganizado
Retornainteger-array: números com os valores diferentes de zero primeiro, na ordem original, e todos os 0 no final

Restrições

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Exemplos

Entrada: nums = [0, 4, 0, 7, 2]
Saída: [4, 7, 2, 0, 0]
Explicação: Os valores que não são 0 são 4, 7 e 2, e eles mantêm essa ordem no início. Os dois 0s ocupam os dois últimos lugares.

+14 testes ocultos ao enviar

Para ir além

Você consegue mover todos os 0 para o início, mantendo os outros valores na ordem em que estão, em uma única passagem e usando memória extra O(1)?

Dicas

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

0 de 3 abertas

Solução

Levar os zeros para o final não é a parte difícil. O difícil é manter os outros valores na ordem original, o que descarta trocar cada 0 pelo último elemento. Divida o array em uma zona inicial que contém os valores não zero encontrados até então e o restante. Um índice lê cada elemento, um segundo marca onde o próximo valor não zero deve ficar, e uma única passagem conclui o trabalho no próprio array.

Copie os valores diferentes de zero

Intuição

Crie um novo array. Percorra nums e copie cada valor que não seja 0, na ordem em que você o encontrar. Depois, adicione zeros até que o novo array tenha o mesmo tamanho que nums. A quantidade de zeros que você adiciona é a quantidade que você ignorou.

Para [0, 4, 0, 7, 2], a etapa de cópia resulta em [4, 7, 2], e dois zeros formam [4, 7, 2, 0, 0]. A ordem está correta porque você copia os valores na ordem em que os lê.

Cada elemento é lido uma vez e escrito uma vez, então o tempo é O(n). O segundo array consome O(n) de memória, o que a próxima abordagem evita.

Algoritmo

Crie um array de resultados vazio.
Para cada valor em nums, adicione-o ao resultado se não for 0.
Adicione zeros até que o resultado tenha tantas entradas quanto nums.
Retorne o resultado.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Dois ponteiros, troca no próprio lugar

Intuição

Use dois índices. read visita todos os elementos da esquerda para a direita. write marca onde o próximo valor diferente de zero deve ficar. Após cada etapa, dois fatos são verdadeiros: tudo antes de write são os valores diferentes de zero vistos até então, na ordem original, e tudo de write até read é 0.

Quando nums[read] não é 0, troque-o com nums[write] e mova write uma posição para a direita. O valor que vai parar em read é um 0 da zona de zeros ou o mesmo valor quando os dois índices são iguais. Os valores diferentes de zero só saltam sobre zeros, nunca uns sobre os outros, então sua ordem é mantida.

[0, 4, 0, 7, 2]: o 4 no índice 1 é trocado com o índice 0, resultando em [4, 0, 0, 7, 2]. O 7 no índice 3 é trocado com o índice 1, resultando em [4, 7, 0, 0, 2]. O 2 no índice 4 é trocado com o índice 2, resultando em [4, 7, 2, 0, 0]. Uma passagem e nenhum segundo array: tempo O(n) e memória O(1).

Algoritmo

Defina write como 0.
Mova read do primeiro índice para o último.
Se nums[read] não for 0, troque nums[read] por nums[write] e, em seguida, some 1 a write.
Retorne nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Armadilhas e casos extremos

Os bugs mais comuns quebram a ordem dos outros valores ou pulam elementos.

Trocar cada 0 pelo último elemento move os zeros, mas embaralha o restante: [0, 4, 7] se torna [7, 4, 0].
Excluir zeros do array enquanto um índice percorre esse array faz com que elementos sejam pulados. Em [0, 0, 5], excluir o índice 0 desloca o segundo 0 para o índice 0 enquanto o loop avança para o índice 1. Cada exclusão também desloca o restante do array, o que torna o loop O(n²).
Teste x != 0, não x > 0. Valores negativos não são zeros: [-1, 0, -2] deve se tornar [-1, -2, 0], mas, com x > 0, a versão que copia retorna [0, 0, 0].
Um array sem zeros ou com apenas zeros deve voltar sem alterações. Na versão com troca, read e write permanecem iguais até o primeiro 0, então essas trocas não alteram nada.
Em Lua e R, os arrays começam em 1, então write também começa em 1.

Perguntas frequentes4

Qual é a complexidade de tempo de Move Zeroes?

O(n). Ambas as abordagens leem cada elemento uma vez. Copiar os valores diferentes de zero para um novo array exige O(n) de memória extra, enquanto a troca com dois ponteiros funciona dentro do array com O(1) de memória extra.

Como mover os zeros para o final sem alterar a ordem dos outros elementos?

Mantenha um índice write para a próxima posição livre no início e percorra com um segundo índice. Cada valor diferente de zero que você encontrar é trocado para a posição write, e write avança uma posição para a direita. Os valores são colocados na ordem em que você os encontra, então a ordem relativa deles nunca muda.

É possível mover zeros com menos gravações?

Sim. Em vez de trocar, copie cada valor diferente de zero para nums[write] e, após a varredura, preencha todos os espaços de write até o final com 0. Assim, cada posição é escrita no máximo uma vez. Você também pode pular uma troca quando read for igual a write, pois ela colocaria um valor de volta onde ele já está.

Por que Move Zeroes é um problema de dois ponteiros?

Um ponteiro lê cada elemento e o outro marca o fim da parte inicial concluída. Ambos avançam apenas, então juntos fazem uma única passagem. O mesmo padrão de leitura e escrita remove duplicatas de um array ordenado ou filtra qualquer valor de um array no próprio lugar.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [0, 4, 0, 7, 2]

Esperado

[4, 7, 2, 0, 0]