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 <[email protected]> wrote: > 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 <[email protected]> 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 <[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. >> > > > > -- > 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 [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. > -- 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.
