Next Permutation

Q: Qual è la complessità temporale di Next Permutation?

O(n) . Una scansione da destra trova il pivot, una seconda trova il valore con cui scambiarlo e un’inversione sistema il suffisso. La memoria aggiuntiva è O(1) , perché tutto avviene all’interno dell’array.

MedioArray e stringhe Due puntatori

+10

Ti viene dato un array di interi nums e i valori possono ripetersi. Immagina tutte le disposizioni distinte di questi valori, ordinate in ordine lessicografico: confronta due disposizioni al primo indice in cui differiscono e quella con il valore più piccolo in quella posizione viene prima. Restituisci la disposizione che viene subito dopo nums in quest’ordine.

Se nums è già la disposizione più grande, non ce n’è una successiva: restituisci la più piccola, cioè i valori ordinati in ordine crescente. Punta a un tempo O(n) e a una memoria aggiuntiva O(1).

Funzione

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

numsinteger-array: la disposizione attuale dei valori
Restituisceinteger-array: la disposizione successiva in ordine lessicografico, oppure i valori ordinati in ordine crescente se nums è il più grande

Vincoli

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Esempi

Input: nums = [2, 5, 4, 1]
Output: [4, 1, 2, 5]
Spiegazione: La coda 5, 4, 1 sta diminuendo, quindi il 2 che la precede deve aumentare. Il valore più piccolo della coda maggiore di 2 è 4; mettilo lì e disponi il resto in ordine crescente: [4, 1, 2, 5].

Input: nums = [3, 2, 2, 1]
Output: [1, 2, 2, 3]
Spiegazione: L'intero array è in ordine decrescente, quindi è la disposizione più grande di 3, 2, 2 e 1. La risposta ricomincia dalla più piccola, [1, 2, 2, 3].

Input: nums = [1, 5, 1]
Output: [5, 1, 1]
Spiegazione: Il primo 1 deve aumentare. L’ultimo 1 è uguale a esso, non maggiore, quindi l’unico valore che può prendere il suo posto è 5, ottenendo [5, 1, 1].

Per approfondire

Come troveresti invece la disposizione precedente, quella che viene subito prima di nums in ordine lessicografico?

Soluzione

Un suffisso decrescente è già grande quanto i suoi valori consentono, quindi la disposizione successiva modifica il valore immediatamente precedente, il pivot. Aumenta il pivot della quantità minima possibile, poi rendi il suffisso il più piccolo possibile. Per farlo, esegui due scansioni da destra e un’inversione, all’interno dell’array.

Disposizioni di elenchi in ordine

Corretto, ma non termina sui test più grandi

Intuizione

Costruisci le disposizioni in profondità a partire dai valori ordinati, provando sempre per primo il valore inutilizzato più piccolo. In questo modo vengono generate in ordine lessicografico, quindi la prima strettamente maggiore di nums è la risposta; se non ce n’è nessuna, restituisci i valori ordinati. I valori ripetuti generano alcune disposizioni due volte, come in 115, 151, 115, 151, 511, 511 per [1, 1, 5], ma una copia ripete solo una disposizione già generata, quindi la prima maggiore è comunque quella successiva.

Il conteggio cresce come n!: 12 valori distinti hanno 479,001,600 disposizioni.

Algoritmo

Ordina una copia di nums in pool.
Crea le disposizioni in profondità, scegliendo le voci non utilizzate di pool da sinistra a destra.
Quando una disposizione è completa, confrontala con nums posizione per posizione.
Restituisci la prima disposizione che è maggiore di nums.
Se nessuna è maggiore, restituisci pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Trova il pivot, scambia, inverti il suffisso

Intuizione

Il pivot è il primo valore da destra più piccolo del suo vicino destro: il 2 in [2, 5, 4, 1]. È la posizione più a destra che può aumentare, e aumentare la posizione più a destra possibile mantiene minimo l’incremento.

Scambia il pivot con il valore più piccolo del suffisso che sia strettamente maggiore. Il suffisso è decrescente, quindi si tratta del valore più a destra maggiore del pivot: 4, ottenendo [4, 5, 2, 1]. Il suffisso rimane decrescente, perché il vecchio pivot si inserisce nella posizione che occupava 4. Ora che la parte iniziale è più grande, il suffisso deve essere il più piccolo possibile, in ordine crescente; invertire una sequenza decrescente permette di farlo: [4, 1, 2, 5].

Senza un pivot, l’array è la disposizione più grande; invertirlo tutto dà quella più piccola. Ogni passaggio richiede una scansione o un’inversione: tempo O(n) e memoria O(1), anche se la versione in R restituisce una copia O(n).

Algoritmo

Imposta i su n-2 e spostalo a sinistra mentre nums[i] ≥ nums[i + 1].
Se i ≥ 0, imposta j su n-1 e spostalo a sinistra mentre nums[j] ≤ nums[i], quindi scambia nums[i] e nums[j].
Inverti la parte da i + 1 fino alla fine usando due indici che si muovono l'uno verso l'altro.
Restituisci nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Trappole e casi limite

Usare > invece di ≥ nella ricerca del pivot. In [3, 2, 2, 1] la coppia 2, 2 non è una salita e fermarsi lì sceglie un pivot che non può crescere.
Scambiare con un valore uguale al pivot. In [1, 5, 1] scambiare i due 1 non cambia nulla; cerca un valore strettamente maggiore.
Scambiare con il valore più grande del suffisso. In [2, 5, 4, 1] questo mette 5 davanti e salta tutte le disposizioni che iniziano con 4.
Saltare il caso senza pivot. La disposizione più grande deve tornare ordinata, invertendo l'intero array.
In Rust, un indice usize che parte da n-2 genera un panic quando n = 1, e andare a sinistra oltre 0 genera un panic quando non c'è un pivot. Usa un indice con segno oppure conta a partire da 1.

Domande frequenti3

Qual è la complessità temporale di Next Permutation?

O(n). Una scansione da destra trova il pivot, una seconda trova il valore con cui scambiarlo e un’inversione sistema il suffisso. La memoria aggiuntiva è O(1), perché tutto avviene all’interno dell’array.

Perché inverti il suffisso invece di ordinarlo?

Dopo lo scambio, il suffisso continua a essere in ordine decrescente, quindi invertirlo lo ordina già in ordine crescente. Un’inversione richiede O(n); un ordinamento produce lo stesso risultato in O(n log n).

Next Permutation funziona con valori duplicati?

Sì, purché entrambi i confronti considerino i valori uguali come non maggiori. La ricerca del pivot salta i valori adiacenti uguali con ≥, e la ricerca dello scambio salta i valori uguali al pivot con ≤. Quindi [1, 5, 1] diventa [5, 1, 1], la successiva disposizione distinta.

def nextPermutation(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

nums = [2, 5, 4, 1]

Output atteso

[4, 1, 2, 5]