Find the Largest Number

Q: Qual è la complessità temporale della ricerca del valore massimo in un array?

Una passata richiede un tempo di O(n) e uno spazio aggiuntivo di O(1) . Nessun metodo su un array non ordinato può fare di meglio, perché qualsiasi elemento che non leggi potrebbe essere il più grande. Ordinare prima costa O(n log n) , che è più lento senza alcun vantaggio.

PrincipianteArray e stringhe

+10

Ricevi una lista non vuota di numeri interi nums. Restituisci il valore più grande al suo interno. I valori possono essere negativi, quindi anche la risposta può essere negativa. Trovalo con i tuoi confronti, senza usare una funzione integrata per trovare il massimo, come max.

Funzione

findMax(nums: integer-array) → integer

numsinteger-array: l’elenco di numeri interi in cui cercare
Restituisceinteger: il valore più grande in nums

Vincoli

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Esempi

Input: nums = [3, 17, 4, 12, 9]
Output: 17
Spiegazione: Leggendo da sinistra, il valore più grande finora è 3, poi 17. Nessuno tra 4, 12 e 9 supera 17, quindi la risposta è 17.

Input: nums = [-8, -3, -11, -3]
Output: -3
Spiegazione: Ogni valore è negativo e -3 è il più vicino allo zero, quindi è il più grande. Compare due volte, ma restituisci il valore, non la sua posizione.

+13 test nascosti all’invio

Per approfondire

Riesci a restituire sia il valore più grande sia quello più piccolo con circa 3n/2 confronti invece di 2n, confrontando prima i valori a coppie?

Suggerimenti

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

0 di 3 aperti

Soluzione

Qualsiasi valore tu salti potrebbe essere il più grande, quindi ogni soluzione legge ogni elemento almeno una volta. L’unica vera decisione è da dove iniziare il massimo corrente. Inizia dal primo elemento, mai da 0, perché ogni valore della lista potrebbe essere negativo.

Ordina una copia e prendi l’ultimo valore

Intuizione

In una lista ordinata dal più piccolo al più grande, il valore più grande si trova alla fine. Copia nums in modo che la lista del chiamante rimanga invariata, ordina la copia e restituisci il suo ultimo elemento. Per [3, 17, 4, 12, 9] la copia ordinata è [3, 4, 9, 12, 17] e l'ultimo elemento è 17.

La risposta è giusta, ma l'ordinamento fa molto più di quanto ti serva. Mette tutti i valori in ordine, il che richiede circa n log n confronti, all'incirca 60,000 per n = 5000, quando vuoi trovare solo il valore più grande. Anche la copia richiede O(n) di memoria.

In JavaScript e TypeScript, passa un comparatore a sort. Senza comparatore, confronta i numeri come testo, mettendo 12 e 17 prima di 3.

Algoritmo

Copia nums.
Ordina la copia dal più piccolo al più grande, confrontando i numeri come numeri.
Restituisci l'ultimo elemento della copia ordinata.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

Un passaggio con un massimo progressivo

Intuizione

Mantieni una variabile, largest, per il valore più grande trovato finora. Inizializzala con nums[0], confrontala con ogni valore e sostituiscila ogni volta che un valore è più grande. Quando il ciclo termina, largest è stato confrontato con ogni elemento, quindi nessun elemento della lista lo supera.

Per [3, 17, 4, 12, 9], largest inizia da 3, diventa 17 e rimane 17 con 4, 12 e 9. Sono n-1 confronti utili e una variabile in più.

È iniziare da nums[0] che permette di gestire le liste di numeri negativi. Se invece inizi da 0, [-8, -3, -11, -3] non lo supera mai, quindi restituisci 0, un valore che non è nemmeno presente nella lista.

Algoritmo

Imposta largest su nums[0].
Scorri ogni valore x in nums.
Se x > largest, imposta largest su x.
Dopo il ciclo, restituisci largest.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

Trappole e casi limite

Il ciclo è breve, quindi gli errori riguardano il valore iniziale e ciò che viene letto.

Inizializzare largest a 0 o -1. Qualsiasi lista i cui valori sono tutti inferiori a quel valore iniziale restituisce un numero che non è nella lista.
Inizializzare a un numero piccolo inventato, come -1000000. I valori qui scendono fino a -10^9, quindi il valore iniziale risulta comunque maggiore. Non c'è bisogno di indovinare nums[0].
Leggere nums[0] in Lua o R, dove il primo elemento è nums[1]. Lua restituisce nil e R restituisce un vettore vuoto.
Usare i ≤ n in un linguaggio con indici a partire da 0: si legge un elemento oltre la fine.
Ordinare senza un comparatore numerico in JavaScript o TypeScript. L'ordine testuale di [3, 17, 4, 12, 9] termina con 9, quindi si restituisce 9 invece di 17.

Domande frequenti4

Qual è la complessità temporale della ricerca del valore massimo in un array?

Una passata richiede un tempo di O(n) e uno spazio aggiuntivo di O(1). Nessun metodo su un array non ordinato può fare di meglio, perché qualsiasi elemento che non leggi potrebbe essere il più grande. Ordinare prima costa O(n log n), che è più lento senza alcun vantaggio.

Come trovi il numero più grande in un array senza usare max?

Memorizza il primo elemento in una variabile. Scorri il resto e, ogni volta che un elemento è più grande della variabile, memorizza quell'elemento al suo posto. Quando il ciclo termina, la variabile contiene il valore più grande.

Perché il massimo corrente dovrebbe iniziare dal primo elemento e non da 0?

Se tutti i valori sono negativi, nessuno di essi è maggiore di 0, quindi un massimo che parte da 0 non cambia mai e la funzione restituisce 0. Il primo elemento è sempre un candidato valido, quindi partire da lì è corretto per qualsiasi lista. Anche il più piccolo intero del tuo linguaggio funziona, purché la lista non sia mai vuota.

Quando l'ordinamento è un buon modo per trovare il valore più grande?

Quando ti serve più del valore massimo, ad esempio i tre valori più grandi o la mediana, e farai molte domande di questo tipo sulla stessa lista. Per trovare un singolo massimo, una sola passata è più veloce e lascia intatta la lista.

Python

def findMax(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [3, 17, 4, 12, 9]

Atteso