• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
60%
SHARE
TWEET

# Find the Intersection of Two Arrays

AaronSawyer Feb 6th, 2013 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //Find The Intersection of Two Arrays
2. //
3. //Given two unsorted arrays as input to a function, find what the intersection (i.e. common
4. //elements) of these two arrays is. For example, with the arrays {1,3,5,7,9,11} and {5,4,3,2,1}
5. //the result would be {1,3,5}.
6. //
7. //For this solution, focus on the efficiency.
8. //
9. // M*(K/2) v K*(M/2) ? it's still O((K*M)/2) compares
10. // Use an output object to eliminate duplicates in the intersection
11. var S={}, res='';
12. function intersect(X,Y,D){"use strict";//if D exists and is non-0, enable debug output to res
13.   var R={},d=D||0,r='',I,J,x=X,y=Y,K,k,n,m,M;
14.   if ((X!==undefined)&&(X!==null)&&((I=X.length)!==0)&&(Y!==undefined)&&(Y!==null)&&((J=Y.length)!==0)) {
15.     K = (I>J)? I : (x=Y,y=X,J) ;  // x is the array arg with more elements, K; we'll walk that
16.     if(d){r+='K='+K+'\n';}
17.     for (n=0,k=0; k<K; ++k){ // k indexes x, the 'larger' array
18.       if(d){r+='x['+k+']='+x[k]+' ';}
19.       for (M=y.length,m=0;m<M;++m){ // m indexes y, the 'smaller' array
20.         if (y[m]===x[k]){R[x[k]]=x[k];if(d){r+='=== y['+m+'] !';}break;}
21.       }
22.       if(d){r+='\n';}
23.     }
24.   }
25.   if(d){res+=r+'\n';}
26.   return R;
27. }
28.
29. //var P=[1,3,5,7,9,11], Q=[5,4,3,2,1];
30.
31. //  P[i]=i*i,-16<i<16; Q[i]=F(i), bidiFibonacci#s, -13<i<13
32. var P=[256,196,169,144,121,100,81, 64, 49,36,25,16,9, 4,1,0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,256],
33.     Q=[           -144, 89,-55,34,-21, 13,-8, 5,-3,2,-1,1,0,1,1,2, 3, 5, 8,13,21,34, 55, 89,144];
34.
35. res+='P=['+P+']\n';
36. res+='Q=['+Q+']\n';
37. res+='\n';
38.
39. S=intersect(Q,P/*,1*/);
40. //res+='S=[';var k=0;for(var s in S){if(Object.prototype.hasOwnProperty.call(S,s)){res+=((k++)?',':'')+s;}};res+=']\n';
41. res+='S=[';var k=0;for(var s in S){res+=((k++)?',':'')+s;};res+=']\n';
42.
43. res;
44.
45. Output#3:
46. P=[256,196,169,144,121,100,81,64,49,36,25,16,9,4,1,0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,256]
47. Q=[-144,89,-55,34,-21,13,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,13,21,34,55,89,144]
48.
49. S=[144,1,0]
RAW Paste Data
Top