Check if an Array Is Sorted
Vous recevez un tableau d’entiers nums. Renvoyez true s’il est trié par ordre non décroissant, c’est-à-dire si chaque élément est inférieur ou égal à celui qui le suit, et false sinon. Les éléments voisins égaux sont acceptés : [2, 2, 3] est considéré comme trié. Un tableau contenant un seul élément est trié.
Fonction
- numsinteger-array
- le tableau d’entiers à vérifier
- Renvoieboolean
- vrai lorsque chaque élément est inférieur ou égal au suivant, faux sinon
Contraintes
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Exemples
- Entrée
- nums = [1, 3, 3, 7]
- Sortie
- true
- Explication
- Chaque étape monte ou reste au même niveau : 1 à 3, 3 à 3, 3 à 7. Le 3 répété est autorisé, donc la réponse est
true.
- Entrée
- nums = [2, 5, 4, 9]
- Sortie
- false
- Explication
- Le passage de 5 à 4 est décroissant. Un seul passage de ce type suffit à rendre le tableau non trié, même si 9 à la fin est la plus grande valeur ; la réponse est donc
false.
+16 tests cachés à la soumission
Pour aller plus loin
Comment vérifieriez-vous en un seul passage un tableau qui peut être trié dans l’un ou l’autre sens, par ordre croissant ou décroissant ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Si un tableau n’est pas trié, où pouvez-vous le constater ? Devez-vous comparer des éléments éloignés les uns des autres ?
Il suffit de comparer chaque élément avec celui qui le suit immédiatement. Les éléments voisins égaux sont autorisés ; seule une diminution rompt l’ordre.
Parcourez les paires voisines et renvoyez
falseà la première paire où la valeur de gauche est supérieure à celle de droite. Si aucune paire de ce type n’existe, renvoyeztrue.
Solution
Un tableau est trié exactement lorsqu’aucun élément n’est supérieur à celui qui le suit immédiatement. Tu n’as jamais besoin de comparer des éléments éloignés : si chaque paire d’éléments voisins est dans le bon ordre, le tableau entier l’est. La vérification se réduit ainsi à un seul parcours des n-1 paires, qui peut s’arrêter au premier ordre décroissant.
Trier une copie et comparer
Intuition
Un tableau trié est un tableau que le tri ne modifierait pas. Faites donc une copie de nums, triez la copie et vérifiez si elle correspond à l’original position par position. Si toutes les positions correspondent, nums était déjà dans l’ordre.
Pour [2, 5, 4, 9], la copie triée est [2, 4, 5, 9]. À la position 1, l’original contient 5 et la copie contient 4 ; la réponse est donc false. Pour [1, 3, 3, 7], la copie est identique et la réponse est true.
C’est correct, mais cela fait plus que ce que demande la question. Le tri coûte O(n log n), soit environ 6 × 10^4 comparaisons pour 5000 nombres, et la copie nécessite O(n) mémoire. Cette méthode parcourt aussi toujours tout le tableau, même lorsque la toute première paire est déjà dans le désordre.
Algorithme
- Copiez
numsafin que l’original reste inchangé. - Triez la copie par ordre numérique croissant.
- Comparez la copie avec
numsposition par position. - Renvoyez
truesi toutes les positions correspondent,falsesinon.
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == numsComparez chaque paire de voisins
Intuition
Tu n’as pas besoin de la version triée pour savoir si le tableau est trié. Un tableau est en ordre non décroissant exactement lorsque chaque élément est inférieur ou égal à celui qui le suit. Comme les chaînes de ≤ (a ≤ b et b ≤ c impliquent a ≤ c), vérifier les n-1 paires voisines couvre toutes les paires de positions.
Parcours i de 1 à n-1 et compare nums[i-1] à nums[i]. Pour [2, 5, 4, 9], la paire (2, 5) convient et la paire (5, 4) descend, donc tu renvoies false à cet instant sans regarder 9. Les voisins égaux conviennent, car seul > échoue.
Chaque paire est comparée une fois, donc le temps d’exécution est O(n), et l’indice de la boucle est la seule mémoire supplémentaire, O(1). Compare directement les deux valeurs plutôt que de les soustraire : avec des valeurs pouvant atteindre 10^9, une différence peut provoquer un dépassement de capacité d’un entier 32 bits.
Algorithme
- Parcourez
ide 1 àn-1. - Si
nums[i-1] > nums[i], renvoyezfalse. - Si la boucle se termine, renvoyez
true. Un élément unique ignore la boucle et est trié.
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
Pièges et cas limites
La boucle est courte : les bogues se trouvent donc à ses limites et dans la comparaison.
- Considérer deux éléments voisins égaux comme un échec. Tester
nums[i-1] >= nums[i]rejette[1, 3, 3, 7]. Seule une étape strictement décroissante (>) rompt l’ordre. - Lire au-delà de la fin. Une boucle allant de
0àn-1qui comparenums[i]ànums[i+1]doit s’arrêter un élément plus tôt, sinon elle lit en dehors du tableau. Commencer ài = 1et comparer aveci-1évite le problème. - Soustraire au lieu de comparer.
nums[i] - nums[i-1] >= 0semble équivalent, mais10^9 - (-10^9) = 2 × 10^9ne tient pas dans un entier signé de 32 bits et déborde en produisant un nombre négatif ; par conséquent,[-1000000000, 1000000000]est signalé comme non trié. Le même débordement affecte un comparateur qsort écrit sous la formex - y. - Trier les nombres comme du texte. En JavaScript,
sort()sans fonction de comparaison place10avant9; une vérification par tri puis comparaison donne donc de mauvaises réponses.
Questions fréquentes4
Comment vérifier si un tableau est trié ?
Comparez chaque élément avec le suivant. Si un élément est supérieur à son voisin de droite, le tableau n’est pas trié et vous pouvez vous arrêter ; si vous atteignez la fin sans en trouver, il est trié. Cela prend un temps de O(n) et un espace supplémentaire de O(1).
Pourquoi suffit-il de vérifier les voisins ?
La relation d’ordre est transitive : si a ≤ b et b ≤ c, alors a ≤ c. Ainsi, lorsque chaque paire d’éléments adjacents est dans l’ordre, toutes les paires de positions le sont aussi. Inversement, tout tableau non trié possède au moins une paire d’éléments adjacents pour laquelle la valeur diminue.
Un tableau dont les éléments sont tous égaux est-il trié ?
En ordre non décroissant, oui : [4, 4, 4] est trié, car aucun élément n’est supérieur au suivant. Si un problème demande plutôt un ordre strictement croissant, modifie le test pour rejeter également les voisins égaux.
Est-ce que je peux trier une copie et la comparer à l’original ?
Oui, et elle donne la bonne réponse, mais elle coûte O(n log n) en temps et O(n) en mémoire supplémentaire pour la copie. La vérification des voisins est plus rapide, ne nécessite aucune copie et peut renvoyer le résultat dès le premier pas vers le bas sans lire le reste.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def isSorted(nums):
# Écrivez le code iciCas 1
Cas 2
Entrée
nums = [1, 3, 3, 7]
Attendu
true