Ce code trouve l'intersection de deux tableaux non triés.
void intersection(int arr1[],int m,int arr2[],int n) //where m=size of arr1 and n=size of arr2
{
map<int,int>mapp;
for(int i=0;i<m;i++)
mapp[arr1[i]]++; //3
for(int i=0;i<n;i++)
{
if(mapp[arr2[i]] >0) //4
{
mapp[arr2[i]]--; //5
cout<<arr2[i] <<endl;
}
}
}
Qu'est-ce qu'il essaie de faire aux lignes 3, 4 et 5?
3 Réponses :
Prenons un tableau arr1 [] = {2, 3, 2, 3, 4, 3}.
Après avoir utilisé ce type de code,
mapp[arr2[i]]--; //5
Le mapp sera stocké comme suit,
mapp [2] = 2
mapp [3] = 3
mapp [4] = 1
Cela signifie qu'un élément unique se répète combien de fois dans arr1.
Revenez maintenant à la partie principale. L'intersection de deux tableaux signifie les éléments qui ont dans les deux tableaux.
for(int i=0;i<m;i++) mapp[arr1[i]]++;
Cette ligne garantit que l'élément arr2 [i] a dans arr1 au moins une fois. Si mapp [arr2 [i]] == 0 cela signifie qu'il n'est pas dans l'arr1 (confus?). Pourquoi je dis arr1. Parce que nous avons itéré le mapp via arr1. Souvenez-vous de ce que vous avez commenté comme "3".
mapp[arr2[i]] >0 //4
Pour votre 5 ...
Voyons un exemple.
Pour chaque élément dans arr2, si cela est également dans arr1, traversez-le simplement. En fait, ce sera l'élément du tableau après l'intersection.
arr1 = { 2 , 2 , 2, 2, 3 grève>, 5}
arr2 = { 2 , 2 , 3 , 4}
Après l'intersection {2, 2, 3}
La chose qui traverse est en fait,
map<int,int>mapp; for(int i=0;i<m;i++) mapp[arr1[i]]++; //3
C'est trop difficile à démontrer de cette manière. Mais j'ai fait de mon mieux :)
L'algorithme utilise une La première itération ne compte que les valeurs qui existent dans le premier tableau. Donc si le premier tableau contient 3,2,3 et 5, l'instruction La deuxième itération passe par le deuxième tableau. Les nombres qui n'étaient pas déjà dans le premier tableau sont ignorés (car la valeur de la carte serait au mieux 0, c'est le but de Pour le nombre correspondant, il diminue le nombre de valeurs sans correspondance dans la carte et affiche la valeur. Donc, si le second tableau contient 1, 3, 5, 3, 3, les itérations ressembleront à ceci L'algorithme affichera les résultats dans l'ordre d'apparition des nombres dans le deuxième tableau. Il remplit malheureusement std :: map pour associer à chaque valeur stockée dans le tableau un décompte du nombre d'occurrences trouvées. La carte est ordonnée. // 3 mettra à jour la carte pour obtenir l'association suivante: 1 -> mapp[1] is 0 so this number is ignored (indeed it was not in the first array)
3 -> mapp[3] is 2 so the count is decreased to 1 and 3 is printed.
5 -> MAPP[5] is 1 so the count is decreased to 0 and 5 is printed,
3 -> mapp[3] is 1 (see above), so the cound is decreased to 0 and 3 is printed
3 -> mapp[3] is 0 (see above), so either 3 was never found in the first array, or all the count occurences were already matched. So nothing is done.
// 4 ). key counter value
2 -> 1
3 -> 2
5 -> 1
mapp avec une valeur 0 pour tous les éléments de arr2 qui ne sont pas déjà dans arr1 , car le fait même d'accéder à un la clé dans la carte avec [] créera une valeur 0 pour elle. Vérification de la présence d'une valeur dans la carte avec .find () code> serait une meilleure approche.
3 : ceci peut être écrit un peu plus clairement comme ceci:
for (int i = 0; i < n; i++) {
int value2 = arr2[i];
int currentCount = mapp[value2];
if (currentCount > 0) {
mapp[value2] = currentCount - 1;
cout << value2 << endl;
}
}
Cela facilite l'interprétation. Stockez toutes les valeurs de arr1 en tant que clés dans mapp et incrémentez sa valeur de 1 chaque fois que la même valeur est atteinte. Ici, nous supposerons que toute valeur doit toujours commencer à 0.
4 : encore une fois, nous allons réécrire ceci pour que cela devienne plus clair:
for (int i = 0; i < m; i++) {
int value1 = arr1[i];
int currentCount = mapp[value1];
mapp[value1] = currentCount + 1;
}
Dans la déclaration if , nous essayons de trouver une valeur déjà existante dans mapp .
Encore une fois, en supposant que les valeurs par défaut sont 0: nous ignorerons toute valeur qui n'a pas été trouvée dans le premier tableau.
S'il est trouvé, son décompte sera supérieur à 0 et on continue à l'intérieur du if .
5 : l'exemple précédent contient la réécriture p>
On n'entre donc le if que lorsque la clé est présente dans arr1 ainsi que dans arr2 .
Si tel est le cas, nous déduisons simplement le compteur de 1 pour qu'il n'apparaisse qu'une fois pour chaque fois que la valeur est dans les deux tableaux.
Tous les trois utilisent des valeurs stockées dans leurs tableaux respectifs comme clés d'une carte associant des valeurs à des compteurs. Et notez que ce code est un chemin potentiel pour comportement indéfini si
m est vrai, en raison de l'utilisation de arr1 [i]à// 4.Peu importe ce que font ces lignes. Le commentaire précédent l'a légèrement abordé, mais sur la base de la description des paramètres et de l'objectif déclaré de cette fonction, il est assez évident que la logique présentée est fondamentalement imparfaite et ne produira pas de résultats corrects.