编程知识 cdmana.com

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

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 frapper53Oh, 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]

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.

C#Méthodes:Dictionnaire

UtiliserDictionaryFonctionnement du Dictionnaire, Passez d'abord le premier tableau dans le Dictionnaire , Ensuite, faites un jugement avec le deuxième tableau !

Code:

public class Solution {
    
    public int[] Intersect(int[] nums1, int[] nums2) {
    
        var dic = new Dictionary<int,int>();
        List<int> list = new List<int>();
        foreach(int n in nums1)
        {
    
            if(dic.ContainsKey(n))
                dic[n]++;
            else
                dic.Add(n,1);
        }
        foreach(int n in nums2)
        {
    
            if(dic.ContainsKey(n)&&dic[n]>0)
            {
    
                dic[n]--;
                list.Add(n);
            }
        }
        return list.ToArray();
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:128 ms,Dans tous les C# Battu dans la soumission99.61%Utilisateurs
Consommation de mémoire:40.4 MB,Dans tous les C# Battu dans la soumission5.26%Utilisateurs de

Java Méthodes:Hashi

Analyse des idées

  • Comme le même nombre peut apparaître plusieurs fois dans les deux tableaux , Il est donc nécessaire de stocker le nombre d'occurrences de chaque numéro dans un tableau de hachage .

  • Pour un nombre ,Son nombre d'occurrences dans l'intersection est égal au nombre minimum d'occurrences de ce nombre dans les deux tableaux.

  • Traversez d'abord le premier tableau , Et enregistrez chaque nombre dans le premier tableau et le nombre d'occurrences correspondantes dans le tableau de hachage , Puis traversez le deuxième tableau , Pour chaque chiffre du deuxième tableau , Si ce nombre existe dans la table de hachage , Ajouter ce nombre à la réponse , Et réduire le nombre d'occurrences de ce nombre dans la table de hachage .

  • Pour réduire la complexité spatiale,Parcourez d'abord le tableau plus court et notez chaque nombre dans le tableau de hachage et le nombre correspondant d'occurrences,Puis traversez le tableau plus long pour obtenir l'intersection.

Veuillez ajouter une description de l'image

Code:

class Solution {
    
    public int[] intersect(int[] nums1, int[] nums2) {
    
        if (nums1.length > nums2.length) {
    
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
    
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
    
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
    
                intersection[index++] = num;
                count--;
                if (count > 0) {
    
                    map.put(num, count);
                } else {
    
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:3 ms,Dans tous les Java  Battu dans la soumission45.01%Utilisateurs de
Consommation de mémoire:38.8 MB,Dans tous les Java Battu dans la soumission5.86%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[] intersect(int[] nums1, int[] nums2) {
    
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
    
            if (nums1[index1] < nums2[index2]) {
    
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
    
                index2++;
            } else {
    
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

Résultats de la mise en œuvre

Adoption
Temps d'exécution:2 ms,Dans tous les Java  Battu dans la soumission77.89%Utilisateurs de
Consommation de mémoire:38.8 MB,Dans tous les Java Battu dans la soumission16.56%Utilisateurs de

Analyse de la complexité

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

Résumé

  • Aujourd'hui, c'est le cinquante - troisiè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/20211014060755147u.html

Scroll to Top