Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Find the Intersection of Two Arrays

By: AaronSawyer on Feb 6th, 2013  |  syntax: JavaScript  |  size: 1.93 KB  |  views: 56  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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]
clone this paste RAW Paste Data