编程知识 cdmana.com

【 algorithme 】 】 』 impression quotidienne de leetcode』 - 54. Troisième plus grand nombre

Veuillez ajouter une description de l'image


Préface

Problème d'algorithme
  • Un problème d'algorithme tous les jours,Est à la fois un processus d'apprentissage,Un autre processus de partage
  • Conseils:Cette colonne résout le problème Tous les langages de programmation sont utilisés C# Et Java Deux façons de résoudre les problèmes
  • Pour rester dans un état d'apprentissage quotidien,Travaillons ensemble pour être le Dieu de l'algorithme🧐!
  • Aujourd'hui, c'est le problème de l'algorithme de retenue de force qui continue de frapper54Oh, mon Dieu.!
Problème d'algorithme

Exemple de question originale:. Troisième plus grand nombre

Pour vous donner un tableau non vide,Retourner dans ce tableau Troisième plus grand nombre .S'il n'existe pas,Renvoie le nombre maximum dans le tableau.

Exemple:

Entrée:[3, 2, 1]
Produits:1
Explication:Le troisième plus grand nombre est 1 .

Exemple 2:

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

Exemple3

Entrée:[2, 2, 3, 1]
Produits:1
Explication:Attention!,Demande de retour au troisième plus grand nombre,Est le troisième plus grand de tous les nombres différents.
Deux valeurs dans cet exemple sont 2 Nombre de,Ils viennent tous en deuxième position.Le troisième plus grand de tous les nombres différents est 1 .

Description:

  • Nombre d'occurrences de chaque élément dans le résultat de sortie,Doit correspondre à la valeur minimale du nombre d'occurrences de l'élément dans les deux tableaux.
  • Nous pouvons ignorer l'ordre des résultats de sortie.

Conseils:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

C#Méthodes:Trier

  • Après avoir trié le tableau de grand à petit , Traverser le tableau depuis le début , En déterminant si les éléments adjacents sont différents , Pour compter le nombre d'éléments différents .

  • Si vous pouviez trouver trois éléments différents , Retour au troisième élément le plus important , Sinon, renvoie le plus grand élément .

Code:

public class Solution {
    
    public int ThirdMax(int[] nums) {
    
        Array.Sort(nums);
        Array.Reverse(nums);
        for (int i = 1, diff = 1; i < nums.Length; ++i) {
    
            if (nums[i] != nums[i - 1] && ++diff == 3) {
     // En ce moment nums[i]  C'est le troisième plus grand nombre 
                return nums[i];
            }
        }
        return nums[0];
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:92 ms,Dans tous les C# Battu dans la soumission58.36%Utilisateurs
Consommation de mémoire:37.4 MB,Dans tous les C# Battu dans la soumission8.56%Utilisateurs de

C#Méthode 2:Rassemblement ordonné

  • On peut traverser le tableau , En même temps, un ensemble ordonné est utilisé pour maintenir les trois premiers nombres dans le tableau .

  • C'est comme ça qu'on traverse un nombre , Insérez - le dans un ensemble ordonné , Si la taille de l'ensemble ordonné dépasse 333, Supprimer le plus petit élément de la collection .

  • Cela garantit que la taille de l'ensemble ordonné est au plus 333, Et une fois la traversée terminée , Si la taille de l'ensemble ordonné est 333, Sa valeur minimale est le troisième plus grand nombre du tableau ;
    Si la taille de l'ensemble ordonné est insuffisante 333, Renvoie la valeur maximale dans l'ensemble ordonné .

Code

public class Solution {
    
    public int ThirdMax(int[] nums) {
    
        SortedSet<int> s = new SortedSet<int>();
        foreach (int num in nums) {
    
            s.Add(num);
            if (s.Count > 3) {
    
                s.Remove(s.Min);
            }
        }
        return s.Count == 3 ? s.Min : s.Max;
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:92 ms,Dans tous les C# Battu dans la soumission58.36%Utilisateurs de
Consommation de mémoire:38.4 MB,Dans tous les C# Battu dans la soumission5.21%Utilisateurs de

Analyse de la complexité

Complexité temporelle:O( n )
Complexité spatiale:O( 1 )

Java Méthode 1:Trier

Analyse des idées

  • Après avoir trié le tableau de grand à petit , Traverser le tableau depuis le début , En déterminant si les éléments adjacents sont différents , Pour compter le nombre d'éléments différents .

  • Si vous pouviez trouver trois éléments différents , Retour au troisième élément le plus important , Sinon, renvoie le plus grand élément .

Code:

class Solution {
    
    public int thirdMax(int[] nums) {
    
        Arrays.sort(nums);
        reverse(nums);
        for (int i = 1, diff = 1; i < nums.length; ++i) {
    
            if (nums[i] != nums[i - 1] && ++diff == 3) {
     // En ce moment nums[i]  C'est le troisième plus grand nombre 
                return nums[i];
            }
        }
        return nums[0];
    }

    public void reverse(int[] nums) {
    
        int left = 0, right = nums.length - 1;
        while (left < right) {
    
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:2 ms,Dans tous les Java  Battu dans la soumission57.82%Utilisateurs de
Consommation de mémoire:38.5 MB,Dans tous les Java Battu dans la soumission16.17%Utilisateurs de

Analyse de la complexité

Complexité temporelle:O( nlogn )
Complexité spatiale:O( logn ) 

JavaMéthode 2:Rassemblement ordonné

  • On peut traverser le tableau , En même temps, un ensemble ordonné est utilisé pour maintenir les trois premiers nombres dans le tableau .

  • C'est comme ça qu'on traverse un nombre , Insérez - le dans un ensemble ordonné , Si la taille de l'ensemble ordonné dépasse 333, Supprimer le plus petit élément de la collection .

  • Cela garantit que la taille de l'ensemble ordonné est au plus 333, Et une fois la traversée terminée , Si la taille de l'ensemble ordonné est 333, Sa valeur minimale est le troisième plus grand nombre du tableau ;
    Si la taille de l'ensemble ordonné est insuffisante 333, Renvoie la valeur maximale dans l'ensemble ordonné .

Code

class Solution {
    
    public int thirdMax(int[] nums) {
    
        TreeSet<Integer> s = new TreeSet<Integer>();
        for (int num : nums) {
    
            s.add(num);
            if (s.size() > 3) {
    
                s.remove(s.first());
            }
        }
        return s.size() == 3 ? s.first() : s.last();
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:4 ms,Dans tous les Java  Battu dans la soumission39.49%Utilisateurs de
Consommation de mémoire:38.3 MB,Dans tous les Java Battu dans la soumission59.56%Utilisateurs de

Analyse de la complexité

Complexité temporelle:O( n )
Complexité spatiale:O( 1 )

Résumé

  • Aujourd'hui, c'est le 54e jour de l'algorithme de retenue de force !
  • Article adopté C#Et Java Deux langages de programmation pour résoudre les problèmes
  • Certaines méthodes sont aussi des références à la force de l'esprit,C'est aussi apprendre et partager,Merci encore aux algorithmes
  • C'est la fin du partage d'algorithmes d'aujourd'hui,A demain!
    Veuillez ajouter une description de l'image

版权声明
本文为[Petit y qui frappe le Code]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211014060755143w.html

Scroll to Top