Mover o valor-alvo para o fim
A missão
Problema
Um editor de playlists quer mover todas as cópias de um id de música para o fim da fila sem embaralhar mais nada. Dada uma lista nums e um valor v, rearranje a lista in-place para que os elementos diferentes de v mantenham sua ordem relativa original no início e todas as cópias de v fiquem no fim. Retorne o mesmo objeto de lista e use só uma quantidade constante de memória extra.
Exemplos
Input: nums = [4, 0, 7, 0, 2], v = 0
Output: [4, 7, 2, 0, 0]
Por quê: 4, 7 e 2 ficam na ordem em que chegaram
Input: nums = [3, 1, 3, 3, 5], v = 3
Output: [1, 5, 3, 3, 3]
Por quê: as três cópias de 3 se juntam no fim
Input: nums = [], v = 9
Output: []
Por quê: edge case: não há nada para mover
Dicas
0 / 3
Montar uma segunda lista com os valores mantidos e outra com as cópias funciona, mas a tarefa pede memória extra constante. Pense em onde o próximo valor mantido deve parar.
Use dois índices na mesma lista: um que lê cada elemento e outro que marca o slot em que o próximo valor mantido será escrito.
Leia da esquerda para a direita e copie cada elemento diferente de v para o slot de escrita, avançando o índice de escrita a cada vez. Quando a leitura terminar, preencha com v todos os slots do índice de escrita até o fim.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- rearrange in place with O(1) extra memory
- other values keep their relative order
Solução
O índice de escrita só se move quando um valor mantido é copiado, então ele nunca ultrapassa o de leitura e nenhum valor mantido é sobrescrito antes de ser lido. Copiar na ordem de leitura preserva de graça a ordem relativa dos valores mantidos. Todo slot depois do último valor mantido precisa guardar uma cópia de v, porque o número de cópias é igual ao número de slots que sobram. O tempo é O(n), com uma passada mais o preenchimento, e o espaço é O(1).
def push_back(nums, v):
write = 0 # slot for the next value we keep in front
for x in nums:
if x != v:
nums[write] = x # copy forward, order is preserved
write += 1
for i in range(write, len(nums)):
nums[i] = v # the leftover slots belong to v
return nums
print(push_back([4, 0, 7, 0, 2], 0)) # -> [4, 7, 2, 0, 0]
print(push_back([3, 1, 3, 3, 5], 3)) # -> [1, 5, 3, 3, 3]
print(push_back([], 9)) # -> []Travou na ideia, e não no código? Move Zeroes explica isso.