Second Largest Number
Ti viene fornita una lista di numeri interi nums. Restituisci il secondo valore distinto più grande: il valore più grande che è strettamente minore del massimo. I valori possono ripetersi, quindi per [5, 5, 3] la risposta è 3, non 5. La lista contiene sempre almeno due valori diversi.
Funzione
- numsinteger-array
- l'elenco di numeri interi, con almeno due valori distinti
- Restituisceinteger
- il valore più grande che è minore del massimo
Vincoli
2 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numscontiene almeno due valori distinti.
Esempi
- Input
- nums = [4, 9, 2, 7, 9]
- Output
- 7
- Spiegazione
- Il massimo è
9. Compare due volte, ma una seconda copia del massimo non conta, quindi la risposta è il valore successivo più basso,7.
- Input
- nums = [-5, -1, -8]
- Output
- -5
- Spiegazione
- Dal più grande al più piccolo, i valori sono
-1,-5,-8. Il secondo più grande è-5, anche se è negativo.
- Input
- nums = [6, 6, 6, 3]
- Output
- 3
- Spiegazione
- Esistono solo due valori distinti,
6e3. Per quante volte si ripeta6, il secondo più grande è3.
+15 test nascosti all’invio
Per approfondire
Riesci a restituire il terzo valore distinto più grande in un solo passaggio, con tre variabili e senza ordinare?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Trovare il massimo richiede una variabile. Cosa ti permetterebbe di ricordare una seconda variabile mentre leggi l’elenco?
Tieni traccia del valore più grande e del secondo valore distinto più grande. Un nuovo valore può superare il più grande, collocarsi strettamente tra i due oppure non cambiare nulla.
Inizializza entrambe le variabili a un valore inferiore a ogni valore consentito. Se
x > largest, spostalargestinseconde memorizzax. Altrimenti, sexè strettamente compreso tra i due, memorizzalo insecond.
Soluzione
Due dettagli rendono questo problema più difficile che trovare il massimo. Il massimo può ripetersi e una ripetizione non deve essere segnalata come il secondo valore più grande. La risposta può essere negativa, quindi una variabile che parte da 0 dà una risposta errata per una lista composta solo da valori negativi. Tenere traccia dei due valori distinti più grandi in un solo passaggio, usando confronti stretti, risolve entrambi i problemi.
Ordina e scendi oltre il massimo
Intuizione
Ordina una copia dal più piccolo al più grande. Il massimo si trova alla fine, eventualmente ripetuto più volte di seguito. Procedi verso sinistra dalla fine oltrepassando ogni copia del massimo; il primo valore diverso è il secondo più grande. Per [6, 6, 6, 3] la copia ordinata è [3, 6, 6, 6]: salti tre 6 e arrivi a 3.
Restituire il penultimo elemento è l’errore classico in questo caso. Per [4, 9, 2, 7, 9] restituisce 9, di nuovo il massimo. La ricerca non può andare oltre l’inizio, perché la lista contiene almeno due valori distinti.
La risposta è corretta, ma l’ordinamento dispone tutti i valori quando ti interessano solo i due più grandi. Richiede O(n log n) tempo e la copia richiede O(n) memoria.
Algoritmo
- Copia
numse ordina la copia dal più piccolo al più grande. - Inizia con l’indice
inell’ultima posizione. - Finché il valore in
iè uguale al massimo, spostaidi una posizione a sinistra. - Restituisci il valore in
i.
def secondLargest(nums):
ordered = sorted(nums)
i = len(ordered) - 1
# Step left past every copy of the maximum.
while ordered[i] == ordered[-1]:
i -= 1
return ordered[i]Due passaggi
Intuizione
Dividi il lavoro in due passaggi. Il primo trova il massimo, come in Trova il numero più grande. Il secondo cerca il valore più grande che sia strettamente minore di quel massimo. Per [4, 9, 2, 7, 9] il primo passaggio trova 9, e il secondo salta entrambi i 9 e mantiene il più grande tra 4, 2 e 7, cioè 7.
Inizia second con un valore inferiore a tutti i valori che la lista può contenere, come il numero intero più piccolo previsto dal tuo linguaggio. La lista contiene almeno due valori distinti, quindi un valore sarà minore del massimo e sostituirà sempre quel valore iniziale.
Ogni passaggio calcola un massimo progressivo, quindi il costo totale è O(n) in termini di tempo e O(1) in termini di spazio. Il costo consiste nel leggere la lista due volte, cosa impossibile quando i valori arrivano uno alla volta e scompaiono dopo averli letti.
Algoritmo
- Scorri
numsuna volta e memorizza il massimo inlargest. - Imposta
secondal di sotto di ogni valore consentito. - Scorri di nuovo. Per ogni
xtale chex < largestex > second, impostasecondsux. - Restituisci
second.
def secondLargest(nums):
largest = nums[0]
for x in nums:
if x > largest:
largest = x
second = float("-inf") # below every allowed value
for x in nums:
if x < largest and x > second:
second = x
return secondUn passaggio per tenere traccia dei primi due
Intuizione
Mantieni due variabili, largest e second, per i due valori distinti più grandi incontrati finora. Ogni nuovo valore x rientra in uno di tre casi. Se x è maggiore di largest, il vecchio largest passa al secondo posto e x occupa il primo. Se x è strettamente compreso tra second e largest, diventa il nuovo second. In ogni altro caso non cambia nulla.
I confronti stretti gestiscono i duplicati. Per [4, 9, 2, 7, 9]: largest diventa 4, poi 9 con second = 4. 2 non cambia nulla, 7 è compreso tra 4 e 9, quindi second = 7, e l'ultimo 9 è uguale a largest, quindi viene ignorato. La risposta è 7.
Inizializza entrambe le variabili a un valore inferiore a qualsiasi valore possibile. Inizializzandole entrambe a 0, si ottiene 0 per [-5, -1, -8], perché nessun valore supera mai 0. Poiché la lista contiene due valori distinti, second alla fine assume sempre un valore effettivamente presente nella lista.
Algoritmo
- Imposta
largestesecondal di sotto di ogni valore consentito. - Scorri ogni valore
xinnums. - Se
x > largest, spostalargestinseconde impostalargestsux. - Altrimenti, se
x < largestex > second, impostasecondsux. - Dopo il ciclo, restituisci
second.
def secondLargest(nums):
# Both start below every allowed value.
largest = second = float("-inf")
for x in nums:
if x > largest:
second = largest # the old maximum drops to second place
largest = x
elif largest > x > second:
second = x
return second
Trappole e casi limite
La maggior parte delle risposte errate dipende dai duplicati del valore massimo o dai valori negativi.
- Restituire il penultimo elemento della lista ordinata. Se il massimo è ripetuto, come in
[4, 9, 2, 7, 9], quello è di nuovo il massimo. - Inizializzare le variabili a
0. Con[-5, -1, -8]nessun valore supera0e restituisci0, un numero che non è nella lista. - Scrivere
x >= largestnel primo caso. Un secondo9sposta quindi il primo9inseconde restituisci9. - Aggiornare
secondsolo quando compare un nuovo massimo. In[10, 20, 15], il15non arriva mai inseconde restituisci10. - Rimuovere i duplicati con un insieme e poi ordinare. Funziona, ma richiede
O(n)di memoria eO(n log n)di tempo per un'operazione che si svolge con un solo passaggio.
Domande frequenti4
Come trovi il secondo numero più grande in un array con un'unica scansione?
Conserva i valori distinti più grande e secondo più grande visti finora. Quando un valore supera il più grande, il vecchio valore più grande passa al secondo posto. Quando un valore si trova strettamente tra i due, sostituisce il secondo. Dopo un passaggio, la variabile second contiene la risposta.
Qual è la complessità temporale per trovare il secondo elemento più grande?
I metodi a una passata e a due passate richiedono entrambi un tempo O(n) e spazio aggiuntivo O(1). Ordinare prima richiede un tempo O(n log n). Non puoi fare meglio di O(n), perché ogni valore deve essere letto almeno una volta.
In che modo i duplicati influiscono sul secondo elemento più grande?
Questo problema chiede il secondo valore distinto più grande, quindi le copie del massimo vengono ignorate. Per [9, 9, 7] la risposta è 7. Alcune versioni della domanda contano invece le posizioni e risponderebbero 9, quindi verifica quale interpretazione è prevista prima di scrivere il codice.
Che cosa dovresti restituire quando non esiste un secondo valore più grande?
Qui non può succedere: la lista contiene sempre due valori distinti. In generale, una lista come [4, 4, 4] non ha una risposta e restituiresti un indicatore come -1 o null, oppure genereresti un errore. Puoi rilevare il caso in cui second conserva ancora il suo valore iniziale dopo il ciclo.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def secondLargest(nums):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [4, 9, 2, 7, 9]
Atteso
7