you didnt mention if duplicate elements should appear in the intersection or not. If no duplicates necessary, then your language may already have intersection between arrays built in. Or you should write an intersection operator/method between arrays (in ruby it is just the "&" operator). My example output:
arrays: 6 elements in each array: 20 range: 1 to 5 array #1: [4, 5, 5, 1, 4, 3, 4, 3, 2, 5, 2, 5, 1, 3, 3, 1, 2, 3, 1, 5] array #2: [2, 2, 3, 5, 2, 5, 1, 1, 2, 3, 1, 1, 2, 5, 3, 2, 3, 3, 2, 2] array #3: [1, 3, 2, 5, 4, 3, 1, 1, 2, 1, 5, 4, 4, 4, 2, 2, 5, 1, 2, 2] array #4: [3, 5, 4, 5, 1, 2, 3, 4, 3, 2, 1, 1, 2, 2, 4, 1, 2, 3, 2, 3] array #5: [2, 1, 5, 2, 1, 4, 3, 2, 3, 1, 2, 4, 4, 2, 4, 5, 5, 3, 5, 5] array #6: [4, 4, 2, 5, 3, 2, 5, 3, 5, 3, 2, 4, 4, 2, 5, 5, 4, 3, 1, 1] intersection: [2, 1, 3] my intersection here is simply ar1 & ar2 & ar3 & ar4 & ar5 & ar6 , no duplicates show up. On Oct 28, 3:09 am, kumar raja <rajkumar.cs...@gmail.com> wrote: > How is it possible to create a hash map using elements as keys and their > counts as values .If we give some key the value is automatically computed by > hash function .If u are given an element/key its index/value is calculated > by hash function.am i corrct?? > > On 27 October 2011 22:36, Nitin Garg <nitin.garg.i...@gmail.com> wrote: > > > > > > > > > > > The hashing solution is similar to the 1st answer > > here<http://stackoverflow.com/questions/2932979/find-a-common-element-with...> > > > A sorting solution will take O(k.n.logn) time > > > On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage <ghat...@gmail.com> wrote: > > >> Don, > >> As you said, the intersection set, won't really be in sorted order as it > >> depends on the elements of the second array, which are unsorted. Still, > >> sorting them wouldn't be much different as it'd be worst case O(n logn).. [ > >> Array 2 == Array 1 ] > >> But sorting the First Array has already cost O(n logn) > > >> So I guess the worse case complexity has to be O(n logn) anyway.. > > >> On Thu, Oct 27, 2011 at 10:54 PM, Dan <dant...@aol.com> wrote: > > >>> Hashing all of the K arrays seems like a bit much. How about this? > > >>> You have K seperate arrays to start with, each array having N > >>> elements (is that correct?). > > >>> 1) Sort the first array. > > >>> 2) Step through the 2nd array, 1 element at a time.... say > >>> Array(2).element(i) > >>> Check to see if the value of Array(2).element(i) is in the first > >>> sorted array. > >>> If it is, add this numeric value to your list of "intersection > >>> elements". > > >>> As you pass through all elements of the 2nd array, the values > >>> found which > >>> are intersecting need to be saved ( maybe in the 1st arrays > >>> space to save > >>> memory). Ideally, these should be saved in sorted order as > >>> they are found. > > >>> ( how you store the sorted array will affect speed of this check > >>> of course. > >>> I'd keep it simple on the 1st round, then optimize the code > >>> once everything > >>> appears to be working well, ie with buckets or pointers or > >>> whatever. How > >>> you determine if an element in array 2 intersects with an > >>> element of array > >>> 1 will depend on how you store your sorted array. You might do > >>> a linear > >>> search or a binary search or a bucket search of some sort ). > > >>> 3) Now... step through the 3rd array, 1 element at a time, looking > >>> to see if each > >>> value is in the just created list of "intersection elements" > > >>> 4) Do the save thing now with each of the remaining original K > >>> arrays. > > >>> Dan :-) > > >>> On Oct 24, 10:17 pm, kumar raja <rajkumar.cs...@gmail.com> wrote: > >>> > Find intersection of K unsorted array of N elements each. Intersection > >>> > consists of elements that appear in all the K arrays. > > >>> > what data structure is useful here?? > > >>> > -- > >>> > Regards > >>> > Kumar Raja > >>> > M.Tech(SIT) > >>> > IIT Kharagpur, > >>> > 10it60...@iitkgp.ac.in > > >>> -- > >>> You received this message because you are subscribed to the Google Groups > >>> "Algorithm Geeks" group. > >>> To post to this group, send email to algogeeks@googlegroups.com. > >>> To unsubscribe from this group, send email to > >>> algogeeks+unsubscr...@googlegroups.com. > >>> For more options, visit this group at > >>>http://groups.google.com/group/algogeeks?hl=en. > > >> -- > >> Anup Ghatage > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algogeeks@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com. > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > Nitin Garg > > > "Personality can open doors, but only Character can keep them open" > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
