Find the Largest Number

Q: Quelle est la complexité temporelle pour trouver le maximum dans un tableau ?

Un seul parcours prend un temps de O(n) et un espace supplémentaire de O(1) . Aucune méthode appliquée à un tableau non trié ne peut faire mieux, car tout élément que vous ne lisez jamais pourrait être le plus grand. Trier d’abord coûte O(n log n) , ce qui est plus lent sans apporter aucun avantage.

DébutantTableaux et chaînes

+10

Vous obtenez une liste non vide d’entiers nums. Renvoyez la plus grande valeur de cette liste. Les valeurs peuvent être négatives, donc la réponse peut l’être aussi. Trouvez-la en effectuant vos propres comparaisons, sans utiliser de fonction intégrée de maximum telle que max.

Fonction

findMax(nums: integer-array) → integer

numsinteger-array: la liste d’entiers à rechercher
Renvoieinteger: la plus grande valeur de nums

Contraintes

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

Exemples

Entrée: nums = [3, 17, 4, 12, 9]
Sortie: 17
Explication: En lisant de gauche à droite, la plus grande valeur jusqu’ici est 3, puis 17. Ni 4, ni 12, ni 9 ne dépasse 17, donc la réponse est 17.

Entrée: nums = [-8, -3, -11, -3]
Sortie: -3
Explication: Toutes les valeurs sont négatives, et -3 est la plus proche de zéro, donc c’est la plus grande. Elle apparaît deux fois, mais tu renvoies la valeur, pas sa position.

+13 tests cachés à la soumission

Pour aller plus loin

Peux-tu renvoyer à la fois la valeur la plus grande et la plus petite en effectuant environ 3n/2 comparaisons au lieu de 2n, en comparant d’abord les valeurs par paires ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Toute valeur que tu ignores pourrait être la plus grande, donc chaque solution lit chaque élément au moins une fois. La seule véritable décision consiste à choisir la valeur de départ du maximum courant. Initialise-le avec le premier élément, jamais à 0, car toutes les valeurs de la liste peuvent être négatives.

Trier une copie et récupérer la dernière valeur

Intuition

Dans une liste triée du plus petit au plus grand, la valeur la plus élevée se trouve à la fin. Copie nums afin que la liste de l’appelant reste inchangée, trie la copie et renvoie son dernier élément. Pour [3, 17, 4, 12, 9], la copie triée est [3, 4, 9, 12, 17], et le dernier élément est 17.

La réponse est correcte, mais le tri fait bien plus que nécessaire. Il met toutes les valeurs dans l’ordre, ce qui nécessite environ n log n comparaisons, soit à peu près 60,000 pour n = 5000, alors que tu ne veux que la plus grande. La copie nécessite aussi O(n) mémoire.

En JavaScript et TypeScript, passe un comparateur à sort. Sans comparateur, les nombres sont comparés comme du texte, ce qui place 12 et 17 avant 3.

Algorithme

Copiez nums.
Triez la copie du plus petit au plus grand, en comparant les nombres comme des nombres.
Retournez le dernier élément de la copie triée.

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

Un passage avec un maximum courant

Intuition

Garde une variable, largest, pour la plus grande valeur rencontrée jusqu’ici. Initialise-la à nums[0], compare-la à chaque valeur et remplace-la dès qu’une valeur est plus grande. À la fin de la boucle, largest a été comparée à chaque élément, donc aucun élément de la liste ne la dépasse.

Pour [3, 17, 4, 12, 9], largest commence à 3, devient 17 et reste à 17 pour 4, 12 et 9. Cela fait n-1 comparaisons utiles et une variable supplémentaire.

Commencer à nums[0] permet de traiter les listes de nombres négatifs. Commence plutôt à 0 et [-8, -3, -11, -3] ne le dépasse jamais : tu renvoies donc 0, une valeur qui ne figure même pas dans la liste.

Algorithme

Définis largest comme nums[0].
Parcours chaque valeur x de nums.
Si x > largest, définis largest comme x.
Après la boucle, renvoie 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

Pièges et cas limites

La boucle est courte, donc les erreurs se trouvent dans son point de départ et dans ce qu’elle lit.

Initialiser largest à 0 ou -1. Toute liste dont les valeurs sont toutes inférieures à cette valeur initiale renvoie un nombre qui ne figure pas dans la liste.
Commencer par un petit nombre choisi arbitrairement, comme -1000000. Les valeurs ici descendent jusqu’à -10^9, donc la valeur initiale reste la plus grande. nums[0] évite toute supposition.
Lire nums[0] en Lua ou en R, où le premier élément est nums[1]. Lua renvoie nil et R renvoie un vecteur vide.
Faire une boucle avec i ≤ n dans un langage où les index commencent à 0, ce qui lit un élément au-delà de la fin.
Trier sans comparateur numérique en JavaScript ou en TypeScript. L’ordre lexicographique de [3, 17, 4, 12, 9] se termine par 9, donc tu renvoies 9 au lieu de 17.

Questions fréquentes4

Quelle est la complexité temporelle pour trouver le maximum dans un tableau ?

Un seul parcours prend un temps de O(n) et un espace supplémentaire de O(1). Aucune méthode appliquée à un tableau non trié ne peut faire mieux, car tout élément que vous ne lisez jamais pourrait être le plus grand. Trier d’abord coûte O(n log n), ce qui est plus lent sans apporter aucun avantage.

Comment trouver le plus grand nombre dans un tableau sans utiliser max ?

Stocke le premier élément dans une variable. Parcours les autres et, chaque fois qu’un élément est plus grand que la variable, stocke cet élément à la place. À la fin de la boucle, la variable contient la plus grande valeur.

Pourquoi le maximum courant doit-il commencer par le premier élément et non par 0 ?

Si toutes les valeurs sont négatives, aucune n’est supérieure à 0, donc un maximum qui commence à 0 ne change jamais et la fonction renvoie 0. Le premier élément est toujours un candidat réel, donc commencer par lui convient pour n’importe quelle liste. L’entier le plus petit de votre langage convient également, tant que la liste n’est jamais vide.

Quand le tri est-il un bon moyen de trouver la plus grande valeur ?

Lorsque vous avez besoin de plus que la valeur maximale, par exemple des trois valeurs les plus élevées ou de la médiane, et que vous poserez de nombreuses questions de ce type sur la même liste. Pour trouver un maximum unique, un seul parcours est plus rapide et ne modifie pas la liste.

Python

def findMax(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu