sorry, i made a slight coding mistake in my last post (invisible 7th array) , but the logic remains the same...corrected sample output:
arrays: 6 elements in each array: 20 range: 1 to 5 array #1: [3, 4, 3, 4, 5, 3, 2, 2, 1, 4, 2, 3, 4, 4, 3, 1, 3, 2, 4, 4] array #2: [1, 4, 5, 2, 1, 5, 1, 4, 3, 1, 3, 2, 5, 4, 4, 1, 3, 4, 5, 3] array #3: [4, 3, 4, 3, 3, 5, 2, 5, 4, 5, 2, 2, 1, 5, 5, 4, 4, 1, 2, 2] array #4: [4, 2, 5, 1, 1, 1, 1, 1, 5, 5, 1, 3, 4, 1, 5, 4, 3, 5, 2, 5] array #5: [3, 4, 2, 5, 1, 4, 1, 5, 5, 5, 3, 5, 2, 1, 4, 1, 1, 5, 2, 5] array #6: [5, 5, 2, 4, 3, 5, 5, 4, 1, 4, 2, 3, 1, 1, 5, 2, 5, 1, 3, 4] intersection: [3, 4, 5, 2, 1] 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.
