Nombre d'éléments communs entre deux tableaux

Version imprimable

bonjour,
étant donné deux tableaux de nombres entiers, j'aimerais trouver le nombre d'éléments communs entre les deux tbleaux:
exemple
nbcommun([1,2,1,3,4],[1,5,4,6]=2)
voici mon code:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 var nbcommun = function(tab1,tab2){ var n=0; var n1=tab1.length; var n2=tab2.length; for(var i=0;i<n1;i++){ for(var j=0;j<n2;j++){ if(tab1[i]==tab2[j]){ n++; break; } } } return n; };
mon code marche bien quand il n'y a pas de doublons, par contre avec les doublons ca ne marche pas
merci de me donner des idées

17/02/2015, 17h52
dinobogan

Pour plus d'efficacité et un code de comparaison plus simple, je te conseille de trier tes deux tableaux.

Qu'entends-tu par doublon ? Par exemple deux fois X dans le premier tableau et une foix X dans le second, le résultat devrait être quoi ?

Sinon, ne serait-ce pas du Javascript ? Car ici, c'est le forum Java, ce qui n'a rien à voir...

EDIT : OK message déplacé
17/02/2015, 18h00
momo-mtl

merci pour cette réponse rapide
oui c'est ca quand il y a deux fois x dans le premier et x dans le deuxième je veut que le résultat soit 1 et non pas 2 ce que me donne mon code
d'autre part on a pas encore vu le tri de tableaux, donc je ne peux pas l'utiliser

ps: oui c du java script!

salut,

dans tes boucles il faut que tu gères les fait que tu sois déjà passé sur un élément ou non.

tu as plusieurs solutions, soit tu boucles une première fois sur tes deux tableaux pour enlever les doublons au sein du même tableau, sois tu stock les éléments sur lesquels tu es déjà passé pour ne pas les recompter.

exemple:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
var nbcommun = function(tab1, tab2) {
    var n = 0;
    var traites = [];
    var traites2 = [];
 
    tab1.forEach(function(item, i, arr) {
        if(traites.indexOf(item) != -1) return; //on test si on a deja traiter ce chiffre
 
        tab2.forEach(function(item2, i2, arr2) {
            if(traites2.indexOf(item2) != -1) return; //on test si on a deja traiter ce chiffre dans le 2eme tab
            if(item == item2) {
                n++;
                traites2.push(item2); //on rajoute le chiffre traiter afin de ne pas le traiter de nouveau
            }
        });
 
        traites.push(item); //on rajoute le chiffre traiter afin de ne pas le traiter de nouveau
    });
 
    return n;
};
 
console.log(nbcommun([1,2,1,3,4],[1,1,1,5,4,6])); //2
console.log(nbcommun([1,2,3,4],[1,5,4,6])); //2
console.log(nbcommun([2,3,4],[1,5,4,6])); //1
console.log(nbcommun([1,2,3,4],[5,6])); //0

y a surement moyen d'optimiser encore tout ça, mais c'est l'idée ;)

Salut !
Tu cherches une fonction d'intersection. Voici une implémentation possible :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
 * @name intersection
 * @description Retourne la liste (sous forme de tableau Array) des éléments communs aux tableaux x et y
 *
 * @param {Array} x - 1er tableau
 * @param {Array} y - 2ème tableau
 *
 * @return {Array} res - intersection de x et y
 */
function intersection(x, y) {
  'use strict';
 
  var i = 0,
      j = 0, 
      res = [],
      xLen = x.length,
      yLen = y.length;
 
  x.sort();
  y.sort();
 
  while (i < xLen && j < yLen) {
    if (x[i] < y[j]) {
      i++;
    } else if (y[j] < x[i]) {
      j++;
    } else {
      res.push(x[i]);
      i++;
      j++;
    }
  }
 
  return res;
}
 
var a = intersection([1,2,1,3,4], [1,5,4,6]);
console.log(a); // [1, 4]
console.log(a.length); // 2

18/02/2015, 13h43
NoSmoking

Bonjour,
@Kaamo : et la version 140 caractères donne quoi ?
:dehors:
18/02/2015, 15h11
momo-mtl

merci pour vos réponses,
Effectivement je cherche une intersection, mais je n'ai pas le droit de déclarer un tableau dont je ne connais pas la taille d'où le calcul du nombre d'éléments communs et je n'ai pas le droit non plus d'utiliser la fonction "push";
18/02/2015, 16h13
Golgotha

Bonjour,

Pour le fun. (uniquement avec FF, qui prends en charge les fonctions fléchées)

function it(x,y){var c=0,o=0; x.sort((a,b) => {return a - b;}).forEach(i => { if (i>o){ if(y.indexOf(i) >= 0) c++; } o=i }); return c; }

:fou:
18/02/2015, 16h34
kakashi99

au vue de ta dernière réponse, ton problème semble être un exo donné par un prof...

si c'est ça, faudrait peut-être nous dire quelles sont les limites... même si sincèrement je ne vois pas le problème de déclarer un tableau vide ou d'utiliser "push".

exactement et les limites c'est qu'on a pas encore vu ni la fonction push ni le tri de tableaux.
finalement j'ai trouvé ceci, apparemment ca marche, vous me direz si on peut l'améliorer

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var nbcommun = function(tab1,tab2){
    var test=false;		
    var n=0;                                
   	for(var i=0;i<tab1.length;i++){	      // on parcours le premier tableau
        for(var k=i+1;k<tab1.length;k++){ // on boucle sur le reste du tableau
            if(tab1[i]==tab1[k]){	      // est ce que ce nombre se répète dans le tableau
                test=true;
                break;
            }
            else test=false;
        }
        if(test==false){				   // si un numéro ne se répète pas on incrémente
            for(var j=0;j<tab2.length;j++){// sinon on incrémente seulement quand on arrive
                if(tab1[i]==tab2[j]){	   //  au dernier numéro de la répétition.
                    n++;
                    break;				  // on sort dès qu'on trouve le premier nombre commun.
                }    
            }
        }
   }
   return n;
};

18/02/2015, 17h34
Golgotha

Comme je disais à mon collègue, imagine si les autres métier prenais exemple sur nous.

J'imagine le chirurgien avec un bout de scotch au bloc : "finalement j'ai trouvé ceci, apparemment ca marche". :aie:

m'enfin...
18/02/2015, 17h42
momo-mtl

ca fait l'affaire c'est l'essentiel lol

Citation:

Envoyé par NoSmoking

Bonjour,
@Kaamo : et la version 140 caractères donne quoi ?
:dehors:

:mrgreen:

119 sans trop optimiser
Code:

1 2 3 (function intersect(x,y){ for(x.sort(y.sort(i=j=0,r=[]));i<x.length&&j<y.length;(x[i]<y[j]&&i++)||(y[j]<x[i]&&j++)||r.push(x[i++])&&j++);return r }([1,2,1,3,4],[1,5,4,6]))

18/02/2015, 18h19
Watilin

Si c'est un exercice ce n'est pas forcément pertinent de chercher la solution sur le Net…

@Golgotha : pas besoin de return avec les fonctions fléchées. Tant qu'on est sous FF, on rajoute un let ? :P

Code:

var it = (x, y) => let (c=0, o=0) x.sort((a,b) => a-b).forEach(i => i>o && y.indexOf(i) >= 0 && c++, o=i), c;
18/02/2015, 19h38
Golgotha

Citation:

Envoyé par Watilin

Si c'est un exercice ce n'est pas forcément pertinent de chercher la solution sur le Net…

@Golgotha : pas besoin de return avec les fonctions fléchées. Tant qu'on est sous FF, on rajoute un let ? :P

Code:

var it = (x, y) => let (c=0, o=0) x.sort((a,b) => a-b).forEach(i => i>o && y.indexOf(i) >= 0 && c++, o=i), c;

:ccool: nice
19/02/2015, 09h37
Spartacusply

Que pensez-vous de la solution proposée par la librairie phpjs ? http://phpjs.org/functions/array_intersect/

Et si c'est pas trop HS d'ailleurs, que pensez-vous de cette librairie ?

Cette fonction ne traite pas les doublons :
Code:

1 2 var a = array_intersect([1,2,1,3,4], [1,5,4,6]); console.log(a); // Object {0: 1, 2: 1, 4: 4}