Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Find The Intersection of Two Arrays
- //
- //Given two unsorted arrays as input to a function, find what the intersection (i.e. common
- //elements) of these two arrays is. For example, with the arrays {1,3,5,7,9,11} and {5,4,3,2,1}
- //the result would be {1,3,5}.
- //
- //For this solution, focus on the efficiency.
- //
- // M*(K/2) v K*(M/2) ? it's still O((K*M)/2) compares
- // Use an output object to eliminate duplicates in the intersection
- var S={}, res='';
- function intersect(X,Y,D){"use strict";//if D exists and is non-0, enable debug output to res
- var R={},d=D||0,r='',I,J,x=X,y=Y,K,k,n,m,M;
- if ((X!==undefined)&&(X!==null)&&((I=X.length)!==0)&&(Y!==undefined)&&(Y!==null)&&((J=Y.length)!==0)) {
- K = (I>J)? I : (x=Y,y=X,J) ; // x is the array arg with more elements, K; we'll walk that
- if(d){r+='K='+K+'\n';}
- for (n=0,k=0; k<K; ++k){ // k indexes x, the 'larger' array
- if(d){r+='x['+k+']='+x[k]+' ';}
- for (M=y.length,m=0;m<M;++m){ // m indexes y, the 'smaller' array
- if (y[m]===x[k]){R[x[k]]=x[k];if(d){r+='=== y['+m+'] !';}break;}
- }
- if(d){r+='\n';}
- }
- }
- if(d){res+=r+'\n';}
- return R;
- }
- //var P=[1,3,5,7,9,11], Q=[5,4,3,2,1];
- // P[i]=i*i,-16<i<16; Q[i]=F(i), bidiFibonacci#s, -13<i<13
- 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],
- 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];
- res+='P=['+P+']\n';
- res+='Q=['+Q+']\n';
- res+='\n';
- S=intersect(Q,P/*,1*/);
- //res+='S=[';var k=0;for(var s in S){if(Object.prototype.hasOwnProperty.call(S,s)){res+=((k++)?',':'')+s;}};res+=']\n';
- res+='S=[';var k=0;for(var s in S){res+=((k++)?',':'')+s;};res+=']\n';
- res;
- Output#3:
- 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]
- 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]
- S=[144,1,0]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement