Find Peak Element

Q: Qual è la complessità temporale di Find Peak Element?

La ricerca binaria richiede un tempo O(log n) e uno spazio O(1) , al massimo 13 passaggi per 5000 valori. La scansione da sinistra richiede O(n) , perché potrebbe leggere ogni coppia prima di trovare il calo.

Q: La ricerca binaria funziona ancora quando ci sono più picchi?

Sì, purché i vicini siano diversi e le posizioni oltre entrambe le estremità siano considerate inferiori a tutti i valori. Restituisce un picco, non sempre quello più alto. Dopo un passo in salita, i valori devono iniziare a scendere entro la fine dell’intervallo, al più tardi, e la prima inversione è un picco, quindi il lato che la ricerca mantiene ne contiene sempre uno.

Q: Il picco è sempre il valore più grande?

In questo problema, sì: l'array sale fino a un picco e poi scende, quindi nessun altro valore può essere più grande. Nella versione con più picchi non è così, perché qualsiasi valore più grande di entrambi i vicini conta. Ecco perché la ricerca confronta i vicini invece di cercare il massimo.

MedioRicerca binaria

+10

L'array nums prima cresce e poi decresce: ogni valore è maggiore di quello precedente fino a un certo indice, e ogni valore dopo quell'indice è minore di quello precedente. Una delle due parti può essere vuota, quindi l'array può solo crescere o solo decrescere. Il valore all'indice di svolta è il picco, l'unico valore maggiore di tutti i suoi vicini.

Restituisci l'indice del picco in tempo O(log n).

Funzione

findPeakElement(nums: integer-array) → integer

numsinteger-array: i valori, che aumentano fino a raggiungere un picco e poi diminuiscono
Restituisceinteger: l'indice del picco

Vincoli

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] per ogni i valido.
nums aumenta strettamente fino a un indice e diminuisce strettamente dopo di esso, quindi c'è esattamente un picco.

Esempi

Input: nums = [2, 5, 9, 4, 1]
Output: 2
Spiegazione: I valori aumentano passando per 2, 5 e 9, poi diminuiscono passando per 4 e 1. L’inversione avviene in corrispondenza di 9, indice 2.

Per approfondire

In una griglia in cui non ci sono due celle adiacenti uguali, un picco è una cella più grande delle sue fino a quattro celle vicine. Riesci a trovarne uno senza leggere tutte le celle?

Suggerimenti

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

0 di 3 aperti

Soluzione

Con un solo picco, il picco è il valore più grande, quindi una scansione lo trova in O(n). Per O(log n), confronta nums[mid] con nums[mid+1]: la pendenza in mid ti dice da quale lato del picco si trova, quindi a ogni passaggio puoi dimezzare l'intervallo.

Cammina finché i valori non iniziano a diminuire

Intuizione

Prima del picco ogni valore è minore del successivo e, a partire dal picco, ogni valore è maggiore. Quindi il picco è il primo indice i per cui nums[i] > nums[i+1], oppure l'ultimo indice se l'array cresce soltanto.

Quando il picco si trova alla fine di 5000 valori, la scansione esegue 4999 confronti, mentre la ricerca binaria ne richiede 13.

Algoritmo

Per i da 0 a n-2, confronta nums[i] con nums[i+1].
Al primo i per cui nums[i] è maggiore, restituisci i.
Se il ciclo termina senza una diminuzione, restituisci n-1.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

Ricerca binaria sulla pendenza

Intuizione

Leggi una coppia, nums[mid] e nums[mid+1]. Un passo in salita significa che l’array sta ancora crescendo, cosa che in questo array accade solo prima del picco: il picco si trova in mid+1 o più a destra. Un passo in discesa significa che sei al picco o lo hai superato: il picco si trova in mid o più a sinistra.

Mantieni un intervallo [lo, hi] che contiene sempre il picco. Un passo in salita sposta lo a mid+1. Un passo in discesa sposta hi a mid, mantenendo mid perché potrebbe essere il picco. Quando lo raggiunge hi, l’unico indice rimasto è il picco. Arrotondare mid per difetto lo mantiene al di sotto di hi, quindi mid+1 esiste sempre.

Nel primo esempio, mid = 2 vede 9 > 4, quindi hi = 2; poi mid = 1 vede 5 < 9, quindi lo = 2, il picco. 5000 valori richiedono al massimo 13 passaggi.

Algoritmo

Imposta lo = 0 e hi = n-1.
Mentre lo < hi, calcola mid = lo + (hi - lo) / 2, arrotondando per difetto.
Se nums[mid] < nums[mid+1], imposta lo = mid + 1.
Altrimenti imposta hi = mid.
Restituisci lo.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

Trappole e casi limite

Impostare hi = mid - 1 quando si scende di un passo. In [2, 5, 9, 4, 1] il primo mid è il picco stesso, e hi = 1 lo scarta; la ricerca restituisce 1.
Confrontare con nums[mid-1] mentre si arrotonda mid per difetto. mid può essere 0, dove non esiste un vicino a sinistra.
Usare un intervallo semiaperto con hi = n. In tal caso mid può essere n-1 e nums[mid+1] accede oltre la fine, subito nel caso di un singolo valore.
Dimenticare lo spostamento in Lua e R. La risposta è comunque l'indice a base 0, quindi una posizione i viene restituita come i-1.

Domande frequenti3

Qual è la complessità temporale di Find Peak Element?

La ricerca binaria richiede un tempo O(log n) e uno spazio O(1), al massimo 13 passaggi per 5000 valori. La scansione da sinistra richiede O(n), perché potrebbe leggere ogni coppia prima di trovare il calo.

La ricerca binaria funziona ancora quando ci sono più picchi?

Sì, purché i vicini siano diversi e le posizioni oltre entrambe le estremità siano considerate inferiori a tutti i valori. Restituisce un picco, non sempre quello più alto. Dopo un passo in salita, i valori devono iniziare a scendere entro la fine dell’intervallo, al più tardi, e la prima inversione è un picco, quindi il lato che la ricerca mantiene ne contiene sempre uno.

Il picco è sempre il valore più grande?

In questo problema, sì: l'array sale fino a un picco e poi scende, quindi nessun altro valore può essere più grande. Nella versione con più picchi non è così, perché qualsiasi valore più grande di entrambi i vicini conta. Ecco perché la ricerca confronta i vicini invece di cercare il massimo.

def findPeakElement(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

nums = [2, 5, 9, 4, 1]

Output atteso