Le problème consiste à identifier le troisième nombre distinct le plus grand au sein d'un tableau d'entiers non vide. Si un tel nombre n'existe pas (c'est-à-dire s'il y a moins de trois nombres distincts dans le tableau), la fonction doit alors retourner le nombre le plus grand du tableau.

Exemples

Exemple 1 :

Entrée : [3, 2, 1]
Sortie : 1
Explication : Le troisième nombre maximum distinct est 1.
   

Exemple 2 :

Entrée : [1, 2]
Sortie : 2
Explication : Le troisième nombre maximum distinct n'existe pas. Le nombre le plus grand est 2.
   

Exemple 3 :

Entrée : [2, 2, 3, 1]
Sortie : 1
Explication : Les nombres distincts sont 1, 2, 3. Le troisième maximum est 1. Les deux instances de '2' comptent pour le deuxième maximum.
   

Contraintes

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

L'objectif est de concevoir une solution avec une complexité temporelle en O(n).

Approche par Parcours Linéaire Unique

Une approche simple pourrait consister à trier le tableau ou à utiliser des structures de données comme des ensembles ordonnés, ce qui mènerait généralement à une complexité en O(n log n). Pour atteindre l'objectif de O(n), nous pouvons parcourir le tableau une seule fois en maintenant à jour les trois nombres distincts les plus grands rencontrés jusqu'à présent.

Pour cela, nous allons utiliser trois variables pour stocker ces valeurs. Lors de l'itération, chaque élément du tableau sera comparé à ces variables. Les valeurs seront "décalées" si un nouvel élément est plus grand que l'une d'entre elles, tout en assurant que nous ne stockons que des valeurs distinctes.

Méthode 1 : Utilisation de valeurs sentinelles (LLONG_MIN)

Nous pouvons initialiser trois variables de type long long (pour éviter les débordements avec INT_MIN et pour avoir une valeur sentinelle suffisamment petite) à la valeur minimale possible (LLONG_MIN). En parcourant le tableau, nous mettons à jour ces variables :

• Si l'élément courant est plus grand que le premier maximum (premierMax), alors troisiemeMax devient deuxiemeMax, deuxiemeMax devient premierMax, et premierMax devient l'élément courant.
• Sinon, si l'élément courant est distinct de premierMax et plus grand que le deuxième maximum (deuxiemeMax), alors troisiemeMax devient deuxiemeMax et deuxiemeMax devient l'élément courant.
• Sinon, si l'élément courant est distinct de premierMax et deuxiemeMax, et plus grand que le troisième maximum (troisiemeMax), alors troisiemeMax devient l'élément courant.

Après le parcours, si la variable du troisième maximum est toujours égale à sa valeur sentinelle, cela signifie qu'il n'y a pas eu trois nombres distincts. Dans ce cas, nous retournons le premier maximum (le plus grand nombre absolu).

#include <vector>
#include <limits> // Pour std::numeric_limits

class Solution {
public:
   int thirdMax(std::vector<int>& nums) {
       long long premierMax = std::numeric_limits<long long>::min();
       long long deuxiemeMax = std::numeric_limits<long long>::min();
       long long troisiemeMax = std::numeric_limits<long long>::min();

       for (int nombreActuel : nums) {
           // Si le nombre actuel est le plus grand trouvé jusqu'à présent
           if (nombreActuel > premierMax) {
               troisiemeMax = deuxiemeMax;
               deuxiemeMax = premierMax;
               premierMax = nombreActuel;
           } 
           // Si le nombre actuel est plus petit que premierMax mais plus grand que deuxiemeMax
           // (et distinct de premierMax, grâce à la condition 'nombreActuel < premierMax')
           else if (nombreActuel < premierMax && nombreActuel > deuxiemeMax) {
               troisiemeMax = deuxiemeMax;
               deuxiemeMax = nombreActuel;
           } 
           // Si le nombre actuel est plus petit que deuxiemeMax mais plus grand que troisiemeMax
           // (et distinct de premierMax et deuxiemeMax)
           else if (nombreActuel < deuxiemeMax && nombreActuel > troisiemeMax) {
               troisiemeMax = nombreActuel;
           }
       }

       // Si troisiemeMax est toujours sa valeur initiale (sentinelle),
       // cela signifie qu'il n'y a pas au moins trois nombres distincts.
       // On retourne alors le nombre le plus grand (premierMax).
       if (troisiemeMax == std::numeric_limits<long long>::min()) {
           return static_cast<int>(premierMax);
       } else {
           return static_cast<int>(troisiemeMax);
       }
   }
};
   

Méthode 2 : Utilisation de std::optional (C++17)

L'utilisation d'une valeur sentinelle comme LLONG_MIN fonctionne bien, mais peut potentiellement poser problème si LLONG_MIN lui-même est une valeur valide dans le tableau et doit être considérée comme un des trois plus grands nombres. Pour une soultion plus robuste et idiomatique en C++17, on peut utiliser std::optional pour représenter le fait qu'une valeur n'a pas encore été définie.

Cela nous permet de distinguer clairement entre "la valeur n'est pas encore trouvée" et "la valeur est LLONG_MIN". Nous utilisnos trois objets std::optional<long long> et gérons leur état has_value().

#include <vector>
#include <optional> // Nécessite C++17

class Solution {
public:
   int thirdMax(std::vector<int>& nums) {
       std::optional<long long> premierMaxOpt;
       std::optional<long long> deuxiemeMaxOpt;
       std::optional<long long> troisiemeMaxOpt;

       for (int nombreActuel : nums) {
           long long val = nombreActuel; // Conversion pour la cohérence de type avec optional

           // Gérer la distinctivité : ignorer si le nombre est déjà l'un des trois maxima
           if (premierMaxOpt.has_value() && val == premierMaxOpt.value()) continue;
           if (deuxiemeMaxOpt.has_value() && val == deuxiemeMaxOpt.value()) continue;
           if (troisiemeMaxOpt.has_value() && val == troisiemeMaxOpt.value()) continue;

           // Logique de mise à jour des trois maxima
           if (!premierMaxOpt.has_value() || val > premierMaxOpt.value()) {
               troisiemeMaxOpt = deuxiemeMaxOpt;
               deuxiemeMaxOpt = premierMaxOpt;
               premierMaxOpt = val;
           } else if (!deuxiemeMaxOpt.has_value() || val > deuxiemeMaxOpt.value()) {
               troisiemeMaxOpt = deuxiemeMaxOpt;
               deuxiemeMaxOpt = val;
           } else if (!troisiemeMaxOpt.has_value() || val > troisiemeMaxOpt.value()) {
               troisiemeMaxOpt = val;
           }
       }

       // Si troisiemeMaxOpt n'a pas de valeur, cela signifie qu'il n'y a pas
       // trois nombres distincts. On retourne alors le plus grand nombre.
       if (troisiemeMaxOpt.has_value()) {
           return static_cast<int>(troisiemeMaxOpt.value());
       } else {
           // Le problème garantit que le tableau n'est pas vide,
           // donc premierMaxOpt aura toujours une valeur ici.
           return static_cast<int>(premierMaxOpt.value());
       }
   }
};
   

Analyse de Complexité

• Complexité temporelle : O(n), où n est la longueur du tableau nums. Nous effectuons un seul parcours du tableau.
• Complexité spatiale : O(1). Nous utilisons un nombre constant de variables pour stocker les trois maxima.