Find Minimum in Rotated Sorted Array

Q: Qual è la complessità temporale della ricerca del minimo in un array ordinato ruotato?

Tempo O(log n) e spazio aggiuntivo O(1) con la ricerca binaria. A ogni passaggio si mantiene una metà dell’intervallo, quindi una lista di 5000 elementi richiede al massimo 13 confronti. La scansione per trovare il punto di discesa è O(n) : legge ogni elemento quando il minimo si trova alla fine.

Q: Perché confrontare nums[mid] con nums[hi] e non con nums[lo]?

Perché nums[hi] determina sempre da quale lato si trova il minimo, mentre nums[lo] no. Se nums[mid] > nums[hi] , i valori devono trovarsi tra mid e hi ; altrimenti nums[mid..hi] è crescente e il minimo si trova in mid o prima. Con nums[lo] , il risultato nums[mid] > nums[lo] è compatibile sia con una lista non ruotata, in cui il minimo è nums[lo] , sia con una ruotata, in cui si trova a destra di mid .

Q: Come si fa a determinare quante volte è stato ruotato un array ordinato?

Esegui la stessa ricerca binaria e restituisci lo , l'indice del minimo, invece di nums[lo] . Se consideri una rotazione come lo spostamento dell'ultimo elemento all'inizio, quell'indice è il numero di rotazioni. Se la consideri come lo spostamento del primo elemento alla fine, come fa questo problema, il numero è (n - lo) mod n : in [11, 13, 15, 17, 2, 5, 9] il minimo è all'indice 4 e 7 meno 4 dà i 3 valori spostati.

Q: La ricerca binaria funziona quando l'array contiene duplicati?

Non è rimasta invariata. In [2, 2, 2, 0, 2] , nums[mid] può essere uguale a nums[hi] , e allora non si può escludere nessuno dei due lati. In questo caso, ridurre l’intervallo con hi = hi - 1 è sicuro, perché una copia di nums[hi] rimane nell’intervallo in corrispondenza di mid , ma una lista di valori uguali con un valore più piccolo nascosto al suo interno richiede poi O(n) .

MedioRicerca binaria

+10

Un elenco di numeri interi distinti è stato ordinato in ordine crescente e poi ruotato: un certo numero di elementi, eventualmente zero, è stato preso dall'inizio e spostato alla fine nello stesso ordine. Per esempio, [2, 5, 9, 11, 13, 15, 17] ruotato di 3 diventa [11, 13, 15, 17, 2, 5, 9]. Ti viene dato l'elenco ruotato nums. Restituisci il suo valore più piccolo in tempo O(log n).

Funzione

findMin(nums: integer-array) → integer

numsinteger-array: l'elenco ordinato e ruotato di numeri interi distinti
Restituisceinteger: il valore più piccolo in nums

Vincoli

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Tutti i valori in nums sono distinti.
nums è una lista crescente ruotata di un certo k con 0 ≤ k < nums.length; k = 0 la lascia non ruotata.

Esempi

Input: nums = [11, 13, 15, 17, 2, 5, 9]
Output: 2
Spiegazione: I valori salgono da 11 a 17 e poi scendono a 2, dove inizia la seconda sequenza. La ricerca vede 17 > 9 all'indice 3, quindi il minimo si trova alla sua destra; poi 5 ≤ 9 e 2 ≤ 5 fanno arretrare hi finché l'intervallo non contiene solo l'indice 4, che contiene 2.

Input: nums = [4, 7, 10, 12]
Output: 4
Spiegazione: Questo elenco è stato ruotato di 0, quindi è ancora ordinato e il minimo è il suo primo valore. Ogni valore centrale è al massimo pari all’ultimo, quindi hi continua a spostarsi a sinistra finché raggiunge l’indice 0, che contiene 4.

Input: nums = [30, -6, 0, 8, 19]
Output: -6
Spiegazione: Quattro valori sono stati spostati dall’inizio alla fine, quindi il valore più grande, 30, ora viene per primo e il minimo, -6, si trova all’indice 1. La ricerca restringe l’intervallo agli indici 0 e 1, vede 30 > -6 e sposta lo a 1.

+17 test nascosti all’invio

Per approfondire

Riesci a restituire il k-esimo valore più piccolo di nums in O(log n) senza ordinarlo?

Suggerimenti

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

0 di 3 aperti

Soluzione

Una lista ordinata ruotata è composta da due sequenze crescenti, [11, 13, 15, 17] e poi [2, 5, 9]. Il minimo è il primo valore della seconda sequenza, subito dopo l’unico punto in cui i valori diminuiscono. Scorrere la lista individua questa diminuzione in O(n). Confrontare un valore centrale con l’ultimo valore dell’intervallo permette di capire da quale lato della diminuzione si trova il valore centrale, quindi la ricerca binaria lo trova in O(log n).

Cammina finché i valori non diminuiscono

Intuizione

In un elenco ordinato, ogni valore è maggiore di quello che lo precede. Ruotando l’elenco, entrambe le sequenze rimangono ordinate e si crea un unico punto in cui questo non vale: il valore più grande seguito da quello più piccolo. Quindi scorri l’elenco da sinistra a destra e restituisci il primo valore più piccolo del suo vicino a sinistra. Se non esiste un valore del genere, l’elenco è stato ruotato di 0 posizioni e il minimo è nums[0].

In [11, 13, 15, 17, 2, 5, 9] lo scorrimento supera 13, 15 e 17, ciascuno maggiore del valore che lo precede, e si ferma all’indice 4, dove 2 è minore di 17. È già meglio che cercare il minimo tra tutti i valori, perché si ferma nel punto in cui il valore diminuisce, ma questo punto può trovarsi ovunque. Quando la rotazione sposta un solo elemento, come in [2, 3, 4, 5, 6, 7, 8, 1], lo scorrimento legge l’intero elenco: 5000 confronti per 5000 elementi, mentre la ricerca binaria ne richiede 13.

Algoritmo

Per ogni indice i da 1 a n-1, confronta nums[i] con nums[i-1].
Se nums[i] < nums[i-1], restituisci nums[i]: la seconda sequenza inizia lì.
Se il ciclo termina, la lista non è stata ruotata: restituisci nums[0].

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Ricerca binaria rispetto all'ultimo valore

Intuizione

Mantieni una promessa: il minimo si trova tra lo e hi, estremi inclusi. All’inizio, l’intervallo comprende l’intera lista. Guarda il valore centrale e confrontalo con nums[hi], l’ultimo valore dell’intervallo.

Se nums[mid] > nums[hi], i valori diminuiscono in un punto tra mid e hi, e il minimo è il valore subito dopo quella discesa, quindi si trova a destra di mid: imposta lo = mid + 1. Altrimenti, nums[mid] < nums[hi] (i valori sono distinti), quindi nums[mid..hi] cresce senza alcuna discesa. Il minimo è dunque nums[mid] o un valore precedente, quindi imposta hi = mid. Non saltare oltre mid: potrebbe essere il minimo. Entrambi gli spostamenti mantengono la promessa e restringono l’intervallo; quando lo raggiunge hi, l’unico valore rimasto è il minimo.

Segui l’esempio iniziale, [11, 13, 15, 17, 2, 5, 9]. L’intervallo da 0 a 6 ha indice centrale 3, valore 17, maggiore di nums[6] = 9, quindi lo diventa 4. L’intervallo da 4 a 6 ha indice centrale 5, valore 5, non maggiore di 9, quindi hi diventa 5. L’intervallo da 4 a 5 ha indice centrale 4, valore 2, non maggiore di 5, quindi hi diventa 4. Restituisci nums[4] = 2.

A ogni passaggio l’intervallo si dimezza, quindi il ciclo viene eseguito al massimo circa log2(n) volte: 13 passaggi per 5000 elementi, con due indici di memoria aggiuntiva.

Algoritmo

Imposta lo = 0 e hi = n-1.
Mentre lo < hi, calcola mid = lo + (hi - lo) / 2.
Se nums[mid] > nums[hi], imposta lo = mid + 1.
Altrimenti, imposta hi = mid.
Quando il ciclo termina, restituisci nums[lo].

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Trappole e casi limite

Il ciclo è lungo quattro righe e ogni riga ha una versione errata allettante.

Scrivere hi = mid - 1 nel secondo ramo. Quel ramo viene eseguito quando mid potrebbe essere proprio il minimo. In [3, 1, 2] il valore centrale 1 non è maggiore di 2, quindi hi scende a 0 e la funzione restituisce 3.
Iterare finché lo ≤ hi. Quando lo è uguale a hi, mid è uguale a entrambi, nums[mid] > nums[hi] è falso e hi = mid non cambia nulla: il ciclo non finisce mai. Fermati quando l'intervallo contiene un solo elemento, con lo < hi.
Confrontare con nums[lo] invece che con nums[hi]. Nella lista non ruotata [1, 2, 3, 4, 5], il valore centrale 3 è maggiore di nums[0] = 1, il che fa sembrare che il calo sia a destra; così la ricerca si allontana dal minimo effettivo all'indice 0 e restituisce 4.
Restituire lo invece di nums[lo]. L'esercizio chiede il valore; l'indice è la risposta a una domanda diversa (vedi le FAQ sul numero di rotazioni).
Supporre che la lista sia stata ruotata. È consentita una rotazione di 0 posizioni e il codice che cerca un calo senza un caso alternativo legge oltre la fine o non restituisce nulla. Restituisci nums[0] quando non esiste alcun calo.

Domande frequenti4

Qual è la complessità temporale della ricerca del minimo in un array ordinato ruotato?

Tempo O(log n) e spazio aggiuntivo O(1) con la ricerca binaria. A ogni passaggio si mantiene una metà dell’intervallo, quindi una lista di 5000 elementi richiede al massimo 13 confronti. La scansione per trovare il punto di discesa è O(n): legge ogni elemento quando il minimo si trova alla fine.

Perché confrontare nums[mid] con nums[hi] e non con nums[lo]?

Perché nums[hi] determina sempre da quale lato si trova il minimo, mentre nums[lo] no. Se nums[mid] > nums[hi], i valori devono trovarsi tra mid e hi; altrimenti nums[mid..hi] è crescente e il minimo si trova in mid o prima. Con nums[lo], il risultato nums[mid] > nums[lo] è compatibile sia con una lista non ruotata, in cui il minimo è nums[lo], sia con una ruotata, in cui si trova a destra di mid.

Come si fa a determinare quante volte è stato ruotato un array ordinato?

Esegui la stessa ricerca binaria e restituisci lo, l'indice del minimo, invece di nums[lo]. Se consideri una rotazione come lo spostamento dell'ultimo elemento all'inizio, quell'indice è il numero di rotazioni. Se la consideri come lo spostamento del primo elemento alla fine, come fa questo problema, il numero è (n - lo) mod n: in [11, 13, 15, 17, 2, 5, 9] il minimo è all'indice 4 e 7 meno 4 dà i 3 valori spostati.

La ricerca binaria funziona quando l'array contiene duplicati?

Non è rimasta invariata. In [2, 2, 2, 0, 2], nums[mid] può essere uguale a nums[hi], e allora non si può escludere nessuno dei due lati. In questo caso, ridurre l’intervallo con hi = hi - 1 è sicuro, perché una copia di nums[hi] rimane nell’intervallo in corrispondenza di mid, ma una lista di valori uguali con un valore più piccolo nascosto al suo interno richiede poi O(n).

Python

def findMin(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [11, 13, 15, 17, 2, 5, 9]

Atteso