The hashing solution is similar to the 1st answer here<http://stackoverflow.com/questions/2932979/find-a-common-element-within-n-arrays>
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.
