Check if an Array Is Sorted
Ti viene fornito un array di numeri interi nums. Restituisci true se è in ordine non decrescente, ovvero se ogni elemento è minore o uguale a quello successivo, e false altrimenti. Gli elementi uguali adiacenti vanno bene: [2, 2, 3] è considerato ordinato. Un array con un solo elemento è ordinato.
Funzione
- numsinteger-array
- l’array di interi da controllare
- Restituisceboolean
- true quando ogni elemento è minore o uguale al successivo, false altrimenti
Vincoli
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Esempi
- Input
- nums = [1, 3, 3, 7]
- Output
- true
- Spiegazione
- Ogni passaggio aumenta o rimane allo stesso livello: da 1 a 3, da 3 a 3, da 3 a 7. Il 3 ripetuto è consentito, quindi la risposta è
true.
- Input
- nums = [2, 5, 4, 9]
- Output
- false
- Spiegazione
- Il passaggio da 5 a 4 è in discesa. Un solo passaggio di questo tipo è sufficiente per rendere l'array non ordinato, anche se 9 alla fine è il valore più grande, quindi la risposta è
false.
+16 test nascosti all’invio
Per approfondire
Come controlleresti un array che potrebbe essere ordinato in una delle due direzioni, crescente o decrescente, sempre in un solo passaggio?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Se un array non è ordinato, dove puoi accorgertene? Devi confrontare elementi molto distanti tra loro?
È sufficiente confrontare ogni elemento con quello subito dopo. Sono ammessi elementi adiacenti uguali; solo un passo verso il basso interrompe l’ordine.
Scorri le coppie adiacenti e restituisci
falsealla prima coppia in cui il valore a sinistra è maggiore di quello a destra. Se non esiste una coppia del genere, restituiscitrue.
Soluzione
Un array è ordinato esattamente quando nessun elemento è più grande di quello immediatamente successivo. Non devi mai confrontare elementi molto distanti tra loro: se ogni coppia di elementi adiacenti è in ordine, lo è l'intero array. Così il controllo si riduce a un'unica scansione delle n-1 coppie, che può interrompersi al primo passo in discesa.
Ordina una copia e confronta
Intuizione
Un array ordinato è un array che l’ordinamento non modificherebbe. Quindi crea una copia di nums, ordina la copia e controlla se corrisponde all’originale posizione per posizione. Se tutte le posizioni corrispondono, nums era già ordinato.
Per [2, 5, 4, 9], la copia ordinata è [2, 4, 5, 9]. La posizione 1 contiene 5 nell’originale e 4 nella copia, quindi la risposta è false. Per [1, 3, 3, 7], la copia è identica e la risposta è true.
È corretto, ma fa più di quanto richiesto dalla domanda. L’ordinamento ha un costo di O(n log n), circa 6 × 10^4 confronti per 5000 numeri, e la copia richiede memoria O(n). Inoltre, legge sempre l’intero array, anche quando la prima coppia è già fuori ordine.
Algoritmo
- Copia
numsin modo che l'originale rimanga invariato. - Ordina la copia in ordine numerico crescente.
- Confronta la copia con
numsposizione per posizione. - Restituisci
truese tutte le posizioni corrispondono, altrimentifalse.
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == numsConfronta ogni coppia di vicini
Intuizione
Non ti serve la versione ordinata per sapere se l'array è ordinato. Un array è in ordine non decrescente esattamente quando ogni elemento è minore o uguale a quello immediatamente successivo. Poiché le relazioni ≤ si concatenano (a ≤ b e b ≤ c implicano a ≤ c), controllare le n-1 coppie adiacenti copre tutte le coppie di posizioni.
Fai scorrere i da 1 a n-1 e confronta nums[i-1] con nums[i]. Per [2, 5, 4, 9], la coppia (2, 5) va bene e la coppia (5, 4) scende, quindi restituisci false subito, senza guardare 9. Le coppie di elementi uguali superano il controllo, perché solo > lo fa fallire.
Ogni coppia viene confrontata una volta, quindi il tempo è O(n), e l'indice del ciclo è l'unica memoria aggiuntiva, O(1). Confronta direttamente i due valori invece di sottrarli: con valori fino a 10^9, una differenza può causare un overflow di un int a 32 bit.
Algoritmo
- Esegui un ciclo con
ida 1 an-1. - Se
nums[i-1] > nums[i], restituiscifalse. - Se il ciclo termina, restituisci
true. Con un solo elemento il ciclo viene saltato e l’array è ordinato.
def isSorted(nums):
for i in range(1, len(nums)):
# One step down anywhere breaks the order.
if nums[i - 1] > nums[i]:
return False
return True
Trappole e casi limite
Il ciclo è breve, quindi gli errori si trovano ai suoi estremi e nel confronto.
- Considerare i valori adiacenti uguali come un errore. Verificare
nums[i-1] >= nums[i]rifiuta[1, 3, 3, 7]. Solo un passaggio strettamente decrescente (>) interrompe l’ordine. - Leggere oltre la fine. Un ciclo da
0an-1che confrontanums[i]connums[i+1]deve fermarsi un elemento prima, altrimenti legge fuori dall’array. Partire dai = 1e confrontare coni-1evita il problema. - Sottrarre invece di confrontare.
nums[i] - nums[i-1] >= 0sembra equivalente, ma10^9 - (-10^9) = 2 × 10^9non rientra in un int a 32 bit e va in overflow, diventando un numero negativo; quindi[-1000000000, 1000000000]viene indicato come non ordinato. Lo stesso overflow compromette un comparatore qsort scritto comex - y. - Ordinare i numeri come testo. In JavaScript,
sort()senza una funzione di confronto mette10prima di9, quindi un controllo basato sull’ordinamento e sul confronto dà risultati errati.
Domande frequenti4
Come si verifica se un array è ordinato?
Confronta ogni elemento con quello successivo. Se un elemento è maggiore del suo vicino a destra, l'array non è ordinato e puoi fermarti; se arrivi alla fine senza trovarne uno, è ordinato. Richiede un tempo di O(n) e uno spazio aggiuntivo di O(1).
Perché è sufficiente controllare i vicini?
La relazione d’ordine è transitiva: se a ≤ b e b ≤ c, allora a ≤ c. Quindi, quando ogni coppia di elementi adiacenti è in ordine, anche ogni coppia di posizioni è in ordine. Viceversa, ogni array non ordinato ha almeno una coppia di elementi adiacenti in cui il valore diminuisce.
Un array con elementi uguali è ordinato?
In ordine non decrescente, sì: [4, 4, 4] è ordinato perché nessun elemento è maggiore del successivo. Se un problema richiede invece un ordine strettamente crescente, modifica il controllo in modo da rifiutare anche i vicini uguali.
Posso ordinare una copia e confrontarla con l’originale?
Sì, e fornisce la risposta corretta, ma richiede un tempo O(n log n) e memoria aggiuntiva O(n) per la copia. Il controllo dei vicini è più veloce, non richiede copie e può restituire il risultato al primo passo in discesa, senza leggere il resto.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def isSorted(nums):
# Scrivi il codice quiCaso 1
Caso 2
Input
nums = [1, 3, 3, 7]
Atteso
true