Remove Duplicates from Sorted Array

Q: Come si rimuovono i duplicati sul posto senza memoria aggiuntiva?

Tieni un indice di scrittura k accanto all’indice di lettura. I primi slot k contengono i valori distinti incontrati finora. Quando il valore che leggi è diverso da nums[k-1] , copialo in nums[k] e incrementa k . L’indice di scrittura non supera mai quello di lettura, quindi nulla viene sovrascritto prima di essere letto.

FacileDue puntatori

+10

Ti viene fornito un array di numeri interi nums ordinato in ordine non decrescente, quindi i valori uguali si trovano uno accanto all'altro. Restituisci i valori distinti di nums, ciascuno una sola volta, nell'ordine in cui compaiono. Per esempio, [2, 2, 5] dà [2, 5].

Funzione

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

numsinteger-array: gli interi, ordinati in ordine non decrescente
Restituisceinteger-array: i valori distinti di nums, in ordine crescente

Vincoli

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums è ordinato in ordine non decrescente.

Esempi

Input: nums = [1, 1, 2, 3, 3, 3]
Output: [1, 2, 3]
Spiegazione: 1 compare due volte e 3 tre volte. Tenendone uno per ciascuno, rimane [1, 2, 3].

Input: nums = [-2, 0, 0, 5]
Output: [-2, 0, 5]
Spiegazione: Si ripete solo 0. I valori negativi funzionano allo stesso modo, quindi la risposta è [-2, 0, 5].

Input: nums = [7, 7, 7]
Output: [7]
Spiegazione: Ogni valore è 7, quindi resta solo un 7.

+15 test nascosti all’invio

Per approfondire

Riesci a farlo usando una memoria aggiuntiva O(1), riscrivendo nums direttamente invece di creare un secondo array?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Rimuovere i duplicati da un array qualsiasi significa ricordare ogni valore che hai visto. L'input ordinato elimina questa necessità: le copie di un valore sono vicine, quindi un valore è nuovo solo quando è diverso dall'ultimo che hai mantenuto. Questo trasforma il compito in un'unica passata con due indici e senza memoria aggiuntiva.

Ricorda i valori visti in un insieme hash

Intuizione

Scorri nums e tieni un insieme dei valori che hai già aggiunto alla risposta. Quando un valore non è nell’insieme, aggiungilo alla risposta e all’insieme; quando invece è presente, saltalo. Per [1, 1, 2, 3, 3, 3] la risposta diventa [1], poi [1, 2], poi [1, 2, 3], e ogni copia successiva viene saltata.

Ogni valore viene aggiunto la prima volta che compare e mai più, nell’ordine in cui lo incontri, quindi la risposta è corretta. Questo approccio non sfrutta mai il fatto che nums sia ordinato; funzionerebbe con qualsiasi array.

La ricerca in un insieme richiede in media O(1), quindi il passaggio richiede O(n) tempo, ma sia l’insieme sia la risposta possono contenere n valori: O(n) spazio aggiuntivo. In C, non essendoci un insieme integrato, un array di flag per i 2 × 10^4 + 1 valori possibili svolge lo stesso compito.

Algoritmo

Crea un insieme vuoto seen e una lista vuota result.
Per ogni valore in nums, controlla se è presente in seen.
Se non è presente, aggiungilo a seen e aggiungilo in coda a result.
Restituisci result.

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

Compattazione sul posto con un puntatore di scrittura

Intuizione

In un input ordinato, tutte le copie di un valore formano un unico gruppo, quindi un valore è nuovo esattamente quando è diverso dall’ultimo valore mantenuto. Per questo serve un confronto, non un insieme.

Usa due indici. L’indice di lettura i visita ogni valore. L’indice di scrittura k segna la fine della parte mantenuta: nums[0] fino a nums[k-1] contiene sempre i valori distinti trovati finora. Inizia con k = 1, poiché il primo valore viene sempre mantenuto. Quando nums[i] è diverso da nums[k-1], copialo in nums[k] e incrementa k.

Con [1, 1, 2, 3, 3, 3]: i = 1 legge un secondo 1 e non succede nulla. i = 2 legge 2, che è diverso da nums[0] = 1, quindi lo inserisce all’indice 1 e k diventa 2. i = 3 scrive 3 all’indice 2 e k diventa 3. Gli ultimi due 3 corrispondono a nums[2] e vengono ignorati. I primi tre elementi ora contengono [1, 2, 3].

La scrittura non supera mai la lettura, perché k è sempre minore o uguale a i, quindi non sovrascrivi mai un valore prima di leggerlo. Un singolo passaggio richiede O(n) tempo e, oltre ai valori restituiti, usi due interi: O(1) spazio aggiuntivo.

Algoritmo

Imposta k = 1: nums[0] viene sempre mantenuto.
Fai scorrere i da 1 fino all'ultimo indice.
Se nums[i] è diverso da nums[k-1], imposta nums[k] = nums[i] e aggiungi 1 a k.
Restituisci i primi k valori di 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]

Trappole e casi limite

Il puntatore di scrittura è semplice, e i suoi bug riguardano il valore con cui fai il confronto.

Confrontare nums[i] con nums[i+1] mentre i arriva fino all’ultimo indice. L’ultimo confronto legge oltre la fine dell’array.
Iniziare con k uguale a 0. Così il primo valore viene confrontato con nums[-1], che è fuori dall’intervallo oppure, in Python, è l’ultimo elemento.
Restituire l’intero array invece dei suoi primi k valori. La parte finale contiene ancora i vecchi valori, quindi [1, 1, 2] verrebbe restituito come [1, 2, 2].
Costruire la risposta iterando su un insieme hash. Nella maggior parte dei linguaggi, un insieme hash non mantiene l’ordine, quindi i valori possono risultare mescolati; aggiungi invece ogni valore a una lista quando lo incontri per la prima volta.
In Lua e R, gli array iniziano da 1. La parte mantenuta va da nums[1] a nums[k], e il confronto va fatto con nums[k], non con nums[k-1].

Domande frequenti4

Qual è la complessità temporale di Remove Duplicates from Sorted Array?

La soluzione con puntatore di scrittura legge ogni valore una sola volta, quindi ha una complessità temporale di O(n). Oltre ai valori che restituisce, usa uno spazio aggiuntivo di O(1): due indici.

Perché l’array deve essere ordinato?

L'ordinamento mette ogni copia di un valore in un'unica sequenza, quindi un valore è nuovo esattamente quando è diverso dall'ultimo valore conservato. In un array non ordinato, una copia può comparire molto lontano dalla prima e serve un insieme hash per ricordare ogni valore già visto, il che richiede O(n) spazio aggiuntivo.

Come si rimuovono i duplicati sul posto senza memoria aggiuntiva?

Tieni un indice di scrittura k accanto all’indice di lettura. I primi slot k contengono i valori distinti incontrati finora. Quando il valore che leggi è diverso da nums[k-1], copialo in nums[k] e incrementa k. L’indice di scrittura non supera mai quello di lettura, quindi nulla viene sovrascritto prima di essere letto.

Come permetteresti a ogni valore di comparire al massimo due volte?

Confronta con il valore che si trova due posizioni indietro nella parte mantenuta anziché una: copia nums[i] quando k < 2 o quando è diverso da nums[k-2]. Se è uguale a nums[k-2], la parte mantenuta termina già con due copie di quel valore. La stessa idea consente al massimo m copie con nums[k-m].

Python

def removeDuplicates(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

[1, 2, 3]