编程知识 cdmana.com

[Algorithm thousand problem Case] ️ Daily leetcode punch ️ - - 52. Intersection of two Arrays

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 frapper52Oh, mon Dieu.!
Problème d'algorithme

Exemple de question originale:Intersection de deux tableaux

Deux tableaux donnés,Écrivez une fonction pour calculer leur intersection.

Exemple:

Entrée:nums1 = [1,2,2,1], nums2 = [2,2]
Produits:[2]

Exemple 2:

Entrée:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Produits:[9,4]
Chaque élément du résultat de sortie doit être unique.
Nous pouvons ignorer l'ordre des résultats de sortie.

C#Méthodes:Trier

  • Calculer l'intersection de deux tableaux , La méthode intuitive est de traverser le tableau nums1, Pour chacun de ces éléments ,Traverser le tableau nums2 Déterminer si l'élément est dans le tableau nums2 Moyenne,Si elle existe,Ajouter l'élément à la valeur de retour.

  • Tableau hypothétique nums1 Et nums2 Les longueurs de mEt n, Traverser le tableau nums1 Besoin O(m) Le temps,Jugement nums1 Si chaque élément est dans le tableau nums2 Besoins moyens O(n) Le temps,Donc la complexité temporelle totale estO(mn).

  • Si vous utilisez une collection de hachage pour stocker des éléments,Peut êtreO(1) Pour déterminer si un élément est dans la collection,Ce qui réduit la complexité temporelle.

  • Utilisez d'abord deux collections pour stocker les éléments de deux tableaux,Et ensuite traverser la plus petite collection,Déterminer si chacun de ces éléments se trouve dans une autre collection,Si l'élément est également dans une autre collection,Ajouter l'élément à la valeur de retour.

  • La complexité temporelle de la méthode peut être réduite à O(m+n)

Code:

public class Solution {
    
    public int[] Intersection(int[] nums1, int[] nums2) {
    
        HashSet<int> set1 = new HashSet<int>();
        HashSet<int> set2 = new HashSet<int>();
        foreach(int num in nums1)
        {
    
            set1.Add(num);
        }
        foreach(int num in nums2)
        {
    
            set2.Add(num);
        }
        return GetIntersection(set1,set2);
    }
    public int[] GetIntersection(HashSet<int> set1,HashSet<int> set2)
    {
    
        if(set1.Count()>set2.Count())
        {
    
            return GetIntersection(set2,set1);
        }
        HashSet<int> intersection = new HashSet<int>();
        foreach(int num in set1)
        {
    
            if(set2.Contains(num))
            {
    
                intersection.Add(num);
            }
        }
        int[] answer = new int[intersection.Count()];
        int i = 0;
        foreach(var num in intersection)
        {
    
            answer[i] = num;
            i++;
        }
        return answer;
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:132 ms,Dans tous les C# Battu dans la soumission97.37%Utilisateurs
Consommation de mémoire:40.6 MB,Dans tous les C# Battu dans la soumission5.26%Utilisateurs de

Java Méthodes:Deux ensembles

Analyse des idées

  • Calculer l'intersection de deux tableaux , La méthode intuitive est de traverser le tableau nums1, Pour chacun de ces éléments ,Traverser le tableau nums2 Déterminer si l'élément est dans le tableau nums2 Moyenne,Si elle existe,Ajouter l'élément à la valeur de retour.

  • Tableau hypothétique nums1 Et nums2 Les longueurs de mEt n, Traverser le tableau nums1 Besoin O(m) Le temps,Jugement nums1 Si chaque élément est dans le tableau nums2 Besoins moyens O(n) Le temps,Donc la complexité temporelle totale estO(mn).

  • Si vous utilisez une collection de hachage pour stocker des éléments,Peut êtreO(1) Pour déterminer si un élément est dans la collection,Ce qui réduit la complexité temporelle.

  • Utilisez d'abord deux collections pour stocker les éléments de deux tableaux,Et ensuite traverser la plus petite collection,Déterminer si chacun de ces éléments se trouve dans une autre collection,Si l'élément est également dans une autre collection,Ajouter l'élément à la valeur de retour.

  • La complexité temporelle de la méthode peut être réduite à O(m+n)

Code:

class Solution {
    
    public int[] intersection(int[] nums1, int[] nums2) {
    
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for (int num : nums1) {
    
            set1.add(num);
        }
        for (int num : nums2) {
    
            set2.add(num);
        }
        return getIntersection(set1, set2);
    }

    public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
    
        if (set1.size() > set2.size()) {
    
            return getIntersection(set2, set1);
        }
        Set<Integer> intersectionSet = new HashSet<Integer>();
        for (int num : set1) {
    
            if (set2.contains(num)) {
    
                intersectionSet.add(num);
            }
        }
        int[] intersection = new int[intersectionSet.size()];
        int index = 0;
        for (int num : intersectionSet) {
    
            intersection[index++] = num;
        }
        return intersection;
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:4 ms,Dans tous les Java  Battu dans la soumission21.31%Utilisateurs de
Consommation de mémoire:38.7 MB,Dans tous les Java Battu dans la soumission28.49%Utilisateurs de

Analyse de la complexité

Complexité temporelle:O( m+n )
Complexité spatiale:O( m+n ) 

JavaMéthode 2:Trier + Double pointeur

  • Si les deux tableaux sont ordonnés , Vous pouvez utiliser la méthode à deux pointeurs pour obtenir l'intersection de deux tableaux .

  • Triez d'abord les deux tableaux , Ensuite, utilisez deux pointeurs pour traverser les deux tableaux .

  • Ce qui est prévisible, c'est que les éléments du tableau des réponses doivent être incrémentaux , Pour garantir le caractère unique de l'élément ajouté , Nous avons besoin de variables d'enregistrement supplémentaires pre Élément représentant la dernière fois que vous avez ajouté un tableau de réponses .

  • Au début, Les deux pointeurs pointent respectivement vers la tête des deux tableaux .Chaque

  • Comparez les nombres dans deux tableaux pointés par deux pointeurs ,Si les deux chiffres ne sont pas égaux,Déplacez le pointeur vers un chiffre plus petit à droite,Si les deux chiffres sont égaux, Et ce nombre n'est pas égal à pre, Ajouter ce numéro à la réponse et mettre à jour pre Variables, Déplacez les deux pointeurs à droite en même temps .

  • Quand au moins un pointeur est hors de portée du tableau ,Fin de la traversée.

Code

class Solution {
    
    public int[] intersection(int[] nums1, int[] nums2) {
    
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[length1 + length2];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
    
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
    
                //  Garantir le caractère unique de l'élément ajouté 
                if (index == 0 || num1 != intersection[index - 1]) {
    
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
    
                index1++;
            } else {
    
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:1 ms,Dans tous les Java  Battu dans la soumission99.93%Utilisateurs de
Consommation de mémoire:38.8 MB,Dans tous les Java Battu dans la soumission8.99%Utilisateurs de

Analyse de la complexité

Complexité temporelle:O( mlogm + nlogn )
Complexité spatiale:O( logm + logn )

Résumé

  • Aujourd'hui, c'est le cinquante - deuxième 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/20211014060755152o.html

Scroll to Top