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 <[email protected]> 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 <[email protected]> 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, > > [email protected] > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
