Second Largest Number

+10

Tu reçois une liste d’entiers nums. Renvoie sa deuxième plus grande valeur distincte : la plus grande valeur strictement inférieure au maximum. Les valeurs peuvent se répéter, donc pour [5, 5, 3], la réponse est 3, et non 5. La liste contient toujours au moins deux valeurs différentes.

Fonction

secondLargest(nums: integer-array) → integer

numsinteger-array: la liste d’entiers, avec au moins deux valeurs distinctes
Renvoieinteger: la plus grande valeur qui est inférieure au maximum

Contraintes

2 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums contient au moins deux valeurs distinctes.

Exemples

Entrée: nums = [4, 9, 2, 7, 9]
Sortie: 7
Explication: Le maximum est 9. Il apparaît deux fois, mais une deuxième occurrence du maximum ne compte pas, donc la réponse est la valeur suivante, 7.

Entrée: nums = [-5, -1, -8]
Sortie: -5
Explication: Du plus grand au plus petit, les valeurs sont -1, -5, -8. La deuxième plus grande est -5, même si elle est négative.

Entrée: nums = [6, 6, 6, 3]
Sortie: 3
Explication: Il n’existe que deux valeurs distinctes, 6 et 3. Quel que soit le nombre de fois où 6 se répète, la deuxième plus grande valeur est 3.

Pour aller plus loin

Peux-tu renvoyer la troisième plus grande valeur distincte en un seul parcours, avec trois variables et sans tri ?

Indices

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

0 sur 3 ouverts

Solution

Deux détails rendent cette tâche plus difficile que de trouver le maximum. Le maximum peut apparaître plusieurs fois, et une valeur répétée ne doit pas être indiquée comme étant la deuxième plus grande. La réponse peut être négative : une variable initialisée à 0 donne une réponse incorrecte pour une liste composée uniquement de valeurs négatives. Suivre les deux valeurs distinctes les plus élevées en un seul parcours, à l’aide de comparaisons strictes, permet de gérer les deux cas.

Trier et descendre au-delà du maximum

Intuition

Triez une copie du plus petit au plus grand. Le maximum se trouve à la fin, éventuellement plusieurs fois de suite. Parcourez la liste depuis la fin vers la gauche en passant devant toutes les occurrences du maximum ; la première valeur différente est la deuxième plus grande. Pour [6, 6, 6, 3], la copie triée est [3, 6, 6, 6] : vous passez devant trois 6 et arrivez à 3.

Renvoyer l’avant-dernier élément est l’erreur classique ici. Pour [4, 9, 2, 7, 9], cela renvoie 9, encore le maximum. Le parcours ne peut pas dépasser le début, car la liste contient au moins deux valeurs distinctes.

La réponse est correcte, mais le tri ordonne toutes les valeurs alors que seules les deux plus grandes vous intéressent. Cela coûte O(n log n) en temps et la copie utilise O(n) en mémoire.

Algorithme

Copiez nums et triez la copie du plus petit au plus grand.
Commencez à la dernière position avec l’indice i.
Tant que la valeur à l’indice i est égale au maximum, déplacez i d’une position vers la gauche.
Renvoyez la valeur à l’indice 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]

Deux passes

Intuition

Divise le travail en deux. Le premier passage trouve le maximum, comme dans Trouver le plus grand nombre. Le second passage cherche la plus grande valeur strictement inférieure à ce maximum. Pour [4, 9, 2, 7, 9], le premier passage trouve 9, et le second ignore les deux 9 et conserve la plus grande valeur parmi 4, 2 et 7, soit 7.

Initialise second à une valeur inférieure à toutes celles que la liste peut contenir, par exemple le plus petit entier que ton langage possède. La liste contient au moins deux valeurs distinctes, donc une valeur est inférieure au maximum et remplace toujours cette valeur initiale.

Chaque passage calcule un maximum courant : le coût total est donc de O(n) en temps et de O(1) en espace. Le coût, c’est de lire la liste deux fois, ce qui est impossible lorsque les valeurs arrivent une par une et disparaissent après leur lecture.

Algorithme

Parcourez nums une fois et stockez la valeur maximale dans largest.
Définissez second à une valeur inférieure à toutes les valeurs autorisées.
Parcourez à nouveau. Pour chaque x tel que x < largest et x > second, définissez second sur x.
Renvoyez 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 second

Un seul parcours pour suivre les deux plus grands

Intuition

Conserve deux variables, largest et second, pour les deux plus grandes valeurs distinctes rencontrées jusqu’à présent. Chaque nouvelle valeur x relève de l’un de trois cas. Si x est supérieure à largest, l’ancienne valeur de largest passe en deuxième position et x prend la première place. Si x se situe strictement entre second et largest, elle devient la nouvelle valeur de second. Dans tous les autres cas, rien ne change.

Les comparaisons strictes permettent de gérer les doublons. Pour [4, 9, 2, 7, 9] : largest devient 4, puis 9, avec second = 4. 2 ne change rien, 7 se situe entre 4 et 9, donc second = 7, et le dernier 9 est égal à largest, donc il est ignoré. La réponse est 7.

Initialise les deux variables à des valeurs inférieures à toutes les valeurs possibles. Les initialiser toutes les deux à 0 renvoie 0 pour [-5, -1, -8], car aucune valeur ne dépasse jamais 0. Comme la liste contient deux valeurs distinctes, second finit toujours par contenir une valeur réelle de la liste.

Algorithme

Initialisez largest et second à une valeur inférieure à toutes les valeurs autorisées.
Parcourez chaque valeur x dans nums.
Si x > largest, déplacez largest dans second et définissez largest sur x.
Sinon, si x < largest et x > second, définissez second sur x.
Après la boucle, renvoyez 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

Pièges et cas limites

La plupart des mauvaises réponses sont dues aux doublons de la valeur maximale ou aux valeurs négatives.

Renvoyer l’avant-dernier élément de la liste triée. En cas de valeur maximale répétée, comme dans [4, 9, 2, 7, 9], il s’agit encore de la valeur maximale.
Initialiser les variables à 0. Pour [-5, -1, -8], aucune valeur ne dépasse 0, et tu renvoies 0, un nombre qui ne figure pas dans la liste.
Écrire x >= largest dans le premier cas. Un deuxième 9 fait alors passer le premier 9 dans second, et tu renvoies 9.
Mettre à jour second uniquement lorsqu’un nouveau maximum apparaît. Dans [10, 20, 15], le 15 n’atteint jamais second, et tu renvoies 10.
Supprimer les doublons à l’aide d’un ensemble, puis trier. Ça fonctionne, mais cette méthode utilise O(n) mémoire et O(n log n) temps pour une tâche qu’un seul parcours suffit à accomplir.

Questions fréquentes3

Comment trouver le deuxième plus grand nombre dans un tableau en un seul parcours ?

Conservez les valeurs distinctes les plus grandes et les deuxièmes plus grandes rencontrées jusqu’ici. Lorsqu’une valeur dépasse la plus grande, l’ancienne plus grande passe à la deuxième place. Lorsqu’une valeur se situe strictement entre les deux, elle remplace la deuxième. Après un seul parcours, la variable second contient la réponse.

Quelle est la complexité temporelle pour trouver le deuxième plus grand élément ?

Les méthodes en un passage et en deux passages prennent toutes deux un temps de O(n) et un espace supplémentaire de O(1). Trier d’abord prend un temps de O(n log n). Impossible de faire mieux que O(n), car chaque valeur doit être lue au moins une fois.

Quel est l’effet des doublons sur le deuxième élément le plus grand ?

Ce problème demande la deuxième plus grande valeur distincte, donc les occurrences du maximum sont ignorées. Pour [9, 9, 7], la réponse est 7. Certaines versions de la question comptent plutôt les positions et répondraient 9 ; vérifie donc laquelle est visée avant de coder.

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

Test #1

Test #2

Test #3

Argument

nums = [4, 9, 2, 7, 9]

Résultat attendu

Second Largest Number

Fonction

Contraintes

Exemples

Indices

Solution

Trier et descendre au-delà du maximum

Deux passes

Un seul parcours pour suivre les deux plus grands

Pièges et cas limites

Questions fréquentes3

Problèmes similaires