First Missing Positive

+10

Ti viene fornito un array non ordinato di interi nums. Restituisci il più piccolo intero positivo (1 o maggiore) che non compare in nums. L’array può contenere numeri negativi, zeri, valori ripetuti e valori molto più grandi della sua lunghezza.

Funzione

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: gli interi non ordinati, che possono ripetersi e possono essere negativi, pari a zero o molto grandi
Restituisceinteger: il più piccolo intero positivo che manca in nums

Vincoli

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
I valori non sono in un ordine particolare e possono ripetersi.

Esempi

Input: nums = [5, -2, 1, 3, 2, 9]
Output: 4
Spiegazione: 1, 2 e 3 sono tutti nell'array e 4 no, quindi la risposta è 4. Il 5 e il 9 non contano una volta che manca un valore più piccolo.

Per approfondire

Riesci a trovare la risposta in tempo O(n) usando solo O(1) di memoria aggiuntiva?

Suggerimenti

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

0 di 3 aperti

Soluzione

L'ordinamento richiede un tempo O(n log n) e un insieme hash O(n) di memoria aggiuntiva. Un limite supera entrambi: n valori coprono al massimo n dei numeri da 1 a n+1, quindi la risposta è al massimo n+1. Contano solo i valori da 1 a n e l'array ha n posizioni per registrarli, quindi la memoria aggiuntiva scende a O(1).

Prova ciascun candidato con una scansione completa

Corretto, ma non termina sui test più grandi

Intuizione

Prova i candidati 1, 2, 3, ... in ordine. Per ciascuno, esamina l’intero array e restituisci il primo candidato che la scansione non trova. Per il limite, non verifichi mai oltre n+1.

Quando l’array contiene i valori da 1 a n, in media ogni candidato viene trovato a metà scansione, quindi con n = 10^4 si effettuano circa n²/2 = 5 × 10^7 confronti.

Algoritmo

Imposta candidate a 1.
Esamina nums alla ricerca di un elemento uguale a candidate, fermandoti al primo.
Se nessun elemento corrisponde, restituisci candidate.
Altrimenti aggiungi 1 a candidate ed esamina di nuovo. Non vai mai oltre n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

Contrassegna i valori da 1 a n in un array di flag

Intuizione

Poiché la risposta è al massimo n+1, salta qualsiasi valore minore di 1 o maggiore di n. Un array booleano present di lunghezza n+1 registra gli altri valori, quindi un valore come 10^9 non viene mai memorizzato. Restituisci il primo v da 1 a n il cui flag è false, oppure n+1 se tutti i flag sono impostati.

Nel primo esempio n = 6: vengono impostati i flag per 1, 2, 3 e 5, -2 e 9 vengono saltati e il primo flag non impostato è 4. Due passaggi lineari richiedono un tempo O(n) e i flag occupano una memoria O(n).

Algoritmo

Crea present, con n+1 flag impostati su false.
Per ogni valore v in nums con 1 ≤ v ≤ n, imposta present[v] su true.
Restituisci il primo v da 1 a n il cui flag è false.
Se non ce n'è nessuno, restituisci n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

Inserisci ogni valore nel proprio slot

Intuizione

Il valore v si trova all'indice v-1. Quando ogni valore da 1 a n è al suo posto, il primo indice i che non contiene i+1 indica la risposta.

A ogni indice, scambia il valore con quello nella posizione che gli spetta, finché è compreso tra 1 e n e la posizione che gli spetta non lo contiene già. Potrebbe essere necessario spostare anche il valore che torna indietro. Controllare la posizione che gli spetta, non i, evita i duplicati: in [1, 1] il secondo 1 trova un 1 all'indice 0 e rimane lì.

Nel primo esempio, l'indice 0 manda il 5 al suo posto, poi il 2 che torna indietro; in seguito l'1 e il 3 vanno al loro posto, lasciando [1, 2, 3, -2, 5, 9]: l'indice 3 è il primo posto errato, quindi la risposta è 4.

Ogni scambio mette definitivamente un valore al suo posto, quindi i cicli interni eseguono al massimo n scambi in totale: tempo O(n) e memoria O(1), tranne che in R, che copia il vettore che modifica.

Algoritmo

Per ogni indice i da 0 a n-1:
Mentre 1 ≤ nums[i] ≤ n e nums[nums[i]-1] ≠ nums[i], scambia nums[i] con nums[nums[i]-1].
Dopo il passaggio di posizionamento, trova il primo indice i per cui nums[i] ≠ i+1 e restituisci i+1.
Se ogni posizione contiene il proprio valore, restituisci n+1.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Trappole e casi limite

Interrompere gli scambi quando nums[i] == i+1 invece di quando la posizione corretta contiene già il valore. Con [1, 1], i due 1 si scambiano all’infinito.
Scambiare con if invece di while. Nel primo esempio, il 2 che torna dall’indice 4 non raggiunge mai l’indice 1 e restituisci 2 invece di 4.
Scrivere nums[i] = nums[nums[i]-1] e poi indicizzare di nuovo con nums[i], leggendo così l’indice della posizione corretta dopo che è cambiato. Salva prima l’indice della posizione corretta.
Saltare il controllo dell’intervallo, che invia 0, -2 o 10^9 a un indice esterno all’array.
Restituire n quando tutte le posizioni sono corrette. Per [4, 2, 1, 3] la risposta è 5.

Domande frequenti3

Qual è la complessità temporale di First Missing Positive?

La soluzione con posizionamento richiede un tempo O(n) e spazio aggiuntivo O(1). Il ciclo while si trova all'interno di un ciclo for, ma ogni scambio colloca un valore nel suo indice finale, quindi l'intera esecuzione effettua al massimo n scambi. La versione con array di flag richiede un tempo O(n) e memoria O(n), mentre la scansione di ogni candidato richiede O(n²).

Perché la risposta non è mai maggiore di n+1?

I numeri da 1 a n+1 sono n+1 valori diversi e un array di lunghezza n contiene al massimo n valori diversi, quindi ne manca uno. La risposta è n+1 esattamente quando l’array contiene tutti i valori da 1 a n.

La soluzione in-place modifica l’array di input?

Sì, riordina i valori. Se chi chiama la funzione ha bisogno dell’ordine originale, copia prima l’array, ripristinando così la memoria aggiuntiva a O(n). Un altro metodo in-place sostituisce ogni valore al di fuori dell’intervallo da 1 a n con n+1, poi segna la presenza di v rendendo negativo nums[v-1]; modifica anche l’array.

def firstMissingPositive(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

nums = [5, -2, 1, 3, 2, 9]

Output atteso

First Missing Positive

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ciascun candidato con una scansione completa

Contrassegna i valori da 1 a n in un array di flag

Inserisci ogni valore nel proprio slot

Trappole e casi limite

Domande frequenti3

Problemi simili