Remover duplicados da lista ordenada
A missão
Problema
Uma lista de inteiros chega em ordem não decrescente, então valores iguais ficam lado a lado, em sequências. Compacte a lista in-place (sem memória extra) para que cada valor distinto apareça exatamente uma vez, na ordem original. Retorne a contagem k de valores distintos; os k primeiros slots devem guardá-los, e o que sobrar depois desses slots é ignorado.
Exemplos
Input: nums = [1, 1, 2, 3, 3, 3]
Output: 3, and nums begins with [1, 2, 3]
Input: nums = [4, 4, 4]
Output: 1, and nums begins with [4]
Por quê: uma sequência longa se reduz a um único valor
Input: nums = []
Output: 0
Por quê: edge case: uma lista vazia não guarda nada
Dicas
0 / 3
A ordenação já fez a parte difícil: um duplicado só pode estar logo ao lado do seu gêmeo, então você nunca precisa procurar na lista inteira.
Mantenha duas posições avançando em velocidades diferentes sobre a mesma lista: uma que inspeciona cada elemento e outra que marca onde o próximo valor mantido deve ficar.
Avance a posição de leitura pela lista. Sempre que o valor ali for diferente do último valor que você manteve, copie-o para a posição de escrita e avance essa posição. No fim, a posição de escrita é igual ao número de valores distintos.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- nums is sorted in non-decreasing order
- compact the list in place
Solução
Dois índices percorrem a mesma lista: um leitor visita cada elemento, e um escritor marca o slot do próximo valor distinto. Como valores iguais ficam adjacentes em uma entrada ordenada, o leitor só precisa comparar com o último valor mantido para detectar uma nova sequência. A cópia só acontece nas fronteiras entre sequências, então nenhuma lista extra é alocada. O tempo é O(n) e o espaço é O(1).
def compact_sorted(nums):
if not nums: # nothing to keep in an empty list
return 0
write = 1 # slot for the next distinct value
for read in range(1, len(nums)):
# sorted input means a new value shows up only at a run boundary
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
a = [1, 1, 2, 3, 3, 3]
print(compact_sorted(a), a[:3]) # -> 3 [1, 2, 3]
b = [4, 4, 4]
print(compact_sorted(b), b[:1]) # -> 1 [4]
print(compact_sorted([])) # -> 0Travou na ideia, e não no código? Dois ponteiros explica isso.