Remove Duplicates from Sorted Array

Q: Como remover duplicatas no próprio lugar sem usar memória extra?

Mantenha um índice de escrita k ao lado do índice de leitura. Os primeiros k espaços contêm os valores distintos encontrados até então. Quando o valor lido for diferente de nums[k-1] , copie-o para nums[k] e avance k . O índice de escrita nunca ultrapassa o índice de leitura, então nada é sobrescrito antes de ser lido.

FácilDois ponteiros

+10

Você recebe um array de números inteiros nums ordenado em ordem não decrescente, então valores iguais ficam lado a lado. Retorne os valores distintos de nums, cada um uma vez, na ordem em que aparecem. Por exemplo, [2, 2, 5] resulta em [2, 5].

Função

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

numsinteger-array: os números inteiros, ordenados em ordem não decrescente
Retornainteger-array: os valores distintos de nums, em ordem crescente

Restrições

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

Exemplos

Entrada: nums = [1, 1, 2, 3, 3, 3]
Saída: [1, 2, 3]
Explicação: 1 aparece duas vezes e 3 aparece três vezes. Manter apenas um de cada resulta em [1, 2, 3].

Entrada: nums = [-2, 0, 0, 5]
Saída: [-2, 0, 5]
Explicação: Apenas 0 se repete. Os valores negativos funcionam da mesma maneira, então a resposta é [-2, 0, 5].

Entrada: nums = [7, 7, 7]
Saída: [7]
Explicação: Todos os valores são 7, então só resta um 7.

+15 testes ocultos ao enviar

Para ir além

Você consegue fazer isso usando memória extra O(1), reescrevendo nums no próprio lugar em vez de criar um segundo array?

Dicas

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

0 de 3 abertas

Solução

Remover duplicatas de um array arbitrário significa lembrar cada valor que você já viu. Uma entrada ordenada elimina essa necessidade: as cópias de um valor são vizinhas, então um valor é novo exatamente quando difere do último que você manteve. Isso transforma a tarefa em uma única passagem com dois índices e sem memória extra.

Lembre-se dos valores vistos em um conjunto hash

Intuição

Percorra nums e mantenha um conjunto dos valores que você já adicionou à resposta. Quando um valor não estiver no conjunto, acrescente-o à resposta e adicione-o ao conjunto; quando estiver, ignore-o. Para [1, 1, 2, 3, 3, 3], a resposta cresce para [1], depois [1, 2], depois [1, 2, 3], e todas as cópias posteriores são ignoradas.

Cada valor é acrescentado na primeira vez que aparece e nunca mais, na ordem em que você o encontra, então a resposta está correta. Essa abordagem nunca usa o fato de que nums está ordenado; ela funcionaria com qualquer array.

As consultas ao conjunto levam O(1) em média, então a passagem tem tempo O(n), mas tanto o conjunto quanto a resposta podem conter n valores: espaço extra O(n). Em C, sem um conjunto integrado, um array de sinalizadores para os 2 × 10^4 + 1 valores possíveis faz o mesmo trabalho.

Algoritmo

Crie um conjunto vazio seen e uma lista vazia result.
Para cada valor em nums, verifique se ele está em seen.
Se não estiver, adicione-o a seen e acrescente-o a result.
Retorne result.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

Compacte no próprio local com um ponteiro de escrita

Intuição

Em uma entrada ordenada, todas as cópias de um valor formam uma sequência, então um valor é novo exatamente quando difere do último valor que você manteve. Isso exige uma comparação, não um conjunto.

Use dois índices. O índice de leitura i percorre todos os valores. O índice de escrita k marca o fim da parte mantida: nums[0] a nums[k-1] sempre contém os valores distintos encontrados até então. Comece com k = 1, já que o primeiro valor é sempre mantido. Quando nums[i] diferir de nums[k-1], copie-o para nums[k] e avance k.

Em [1, 1, 2, 3, 3, 3]: i = 1 lê um segundo 1 e nada acontece. i = 2 lê 2, que difere de nums[0] = 1, então ele vai para o índice 1 e k passa a ser 2. i = 3 escreve 3 no índice 2 e k passa a ser 3. Os dois últimos 3s correspondem a nums[2] e são ignorados. Agora os três primeiros espaços contêm [1, 2, 3].

A escrita nunca ultrapassa a leitura, porque k é sempre menor ou igual a i, então você nunca sobrescreve um valor antes de lê-lo. Uma única passagem leva tempo O(n) e, além dos valores retornados, você usa dois inteiros: espaço extra O(1).

Algoritmo

Defina k = 1: nums[0] é sempre mantido.
Percorra i de 1 até o último índice.
Se nums[i] for diferente de nums[k-1], defina nums[k] = nums[i] e some 1 a k.
Retorne os primeiros k valores de nums.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

Armadilhas e casos extremos

O ponteiro de escrita é simples, e seus bugs têm a ver com qual valor você compara.

Comparar nums[i] com nums[i+1] enquanto i percorre até o último índice. A última comparação lê uma posição além do fim do array.
Começar k em 0. Então, o primeiro valor é comparado com nums[-1], que está fora do intervalo ou, em Python, é o último elemento.
Retornar o array inteiro em vez dos primeiros k valores. O restante ainda contém valores antigos, então [1, 1, 2] seria retornado como [1, 2, 2].
Construir a resposta iterando sobre um conjunto hash. Na maioria das linguagens, um conjunto hash não mantém a ordem, então os valores podem sair embaralhados; em vez disso, acrescente cada valor a uma lista quando o encontrar pela primeira vez.
Em Lua e R, os arrays começam em 1. A parte mantida vai de nums[1] a nums[k], e a comparação é feita com nums[k], não com nums[k-1].

Perguntas frequentes4

Qual é a complexidade de tempo de Remove Duplicates from Sorted Array?

A solução com ponteiro de escrita lê cada valor uma vez, portanto é executada em tempo O(n). Além dos valores que retorna, usa espaço extra O(1): dois índices.

Por que o array precisa estar ordenado?

A ordenação coloca todas as cópias de um valor em uma sequência, então um valor é novo exatamente quando difere do último valor mantido. Em um array não ordenado, uma cópia pode aparecer longe da primeira, e você precisa de um conjunto hash para lembrar todos os valores vistos, o que custa O(n) de espaço extra.

Como remover duplicatas no próprio lugar sem usar memória extra?

Mantenha um índice de escrita k ao lado do índice de leitura. Os primeiros k espaços contêm os valores distintos encontrados até então. Quando o valor lido for diferente de nums[k-1], copie-o para nums[k] e avance k. O índice de escrita nunca ultrapassa o índice de leitura, então nada é sobrescrito antes de ser lido.

Como você permitiria que cada valor aparecesse no máximo duas vezes?

Compare com o valor duas posições atrás na parte mantida, em vez de uma: copie nums[i] quando k < 2 ou quando ele for diferente de nums[k-2]. Se for igual a nums[k-2], a parte mantida já termina com duas cópias dele. A mesma ideia permite no máximo m cópias com nums[k-m].

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [1, 1, 2, 3, 3, 3]

Esperado

[1, 2, 3]