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.
