Can't we do this using map library function..mapping the integer with their frequency count??
On Sun, May 15, 2011 at 10:15 PM, Dave <dave_and_da...@juno.com> wrote: > @Akshata: Yes. In my response of May 7, I proposed an algorithm using > hashing. On May 9, Apoorve asked if there was an in-place O(n) > solution. I take it that in-place means with only O(1) extra space. > That is the question to which I was responding. Your suggestion of > using a hashmap is non-responsive since it uses more than O(1) extra > space. > > Dave > > On May 15, 9:49 am, Akshata Sharma <akshatasharm...@gmail.com> wrote: > > hash all the elements. Keys are stored in hashmap in sorted order based > on > > values. just iterate thru the hashmap extracting the first k keys. > > m I missing something? > > > > > > > > On Thu, May 12, 2011 at 2:50 AM, Dave <dave_and_da...@juno.com> wrote: > > > @Apoorve: I don't believe that you can determine the frequency counts > > > in-place in O(n). > > > > > Dave > > > > > On May 9, 8:42 am, Apoorve Mohan <apoorvemo...@gmail.com> wrote: > > > > @Dave: Can there be an in-place O(n) solution to this??? > > > > > > On Mon, May 9, 2011 at 7:01 PM, Dave <dave_and_da...@juno.com> > wrote: > > > > > @Ashish: By compress, I meant to transfer the active entries in the > > > > > hash table into contiguous elements of an array. Since the hash > table > > > > > itself is probably stored in an array, it just means to go through > the > > > > > hash table array and move the active entries to the front of the > > > > > array. > > > > > > > Dave > > > > > > > On May 9, 1:14 am, Ashish Goel <ashg...@gmail.com> wrote: > > > > > > Dave, > > > > > > w.r.t statement, After all integers are processed, compress out > the > > > > > unused > > > > > > hash table > > > > > > entries and find the Kth largest element, > > > > > > > > I could not understand the compress concept...are you saying > > > something on > > > > > > counting sort philosophy? > > > > > > say the list is > > > > > > > > 5 > > > > > > 4 > > > > > > 4 > > > > > > 3 > > > > > > 3 > > > > > > 3 > > > > > > 2 > > > > > > 2 > > > > > > 2 > > > > > > 2 > > > > > > 1 > > > > > > 1 > > > > > > 1 > > > > > > 1 > > > > > > 1 > > > > > > > > so the hash map will have > > > > > > > > 5,1 <5 is 1 time> > > > > > > 4,2,<4 is two time> > > > > > > 3,3,... > > > > > > 2,4,... > > > > > > 1,5... > > > > > > > > so if the question is to find say 3rd largest element based on > > > frequency, > > > > > it > > > > > > would be 4 > > > > > > This essentially means that we probably need dynamic order > statistics > > > > > where > > > > > > the node contains the starting rank for a particular entry in the > > > RBTree. > > > > > > Each RBTree node contains the number, its frequency and rank. > then > > > this > > > > > > becomes O(n) +O(lgn) i.e. O(n) > > > > > > > > Best Regards > > > > > > Ashish Goel > > > > > > "Think positive and find fuel in failure" > > > > > > +919985813081 > > > > > > +919966006652 > > > > > > > > On Sat, May 7, 2011 at 11:03 PM, Dave <dave_and_da...@juno.com> > > > wrote: > > > > > > > @Gaurav: As I understand your solution, you are finding the K > > > largest > > > > > > > integers based on value, rather than the K with the highest > > > frequency > > > > > > > of occurrence. > > > > > > > > > @Amit: Hash the integers into a hash table that includes a > field > > > for > > > > > > > the frequency count. When a new entry is made, set the > frequency > > > count > > > > > > > to 1. When an integer already is in the table, increment its > count. > > > > > > > After all integers are processed, compress out the unused hash > > > table > > > > > > > entries and find the Kth largest element. The overall algorithm > can > > > be > > > > > > > done in O(n). > > > > > > > > > Dave > > > > > > > > > On May 7, 12:06 pm, Gaurav Aggarwal <0007gau...@gmail.com> > wrote: > > > > > > > > It can be done without sorting. Take the first element as > pivot > > > > > > > > element. Calculate its position using Partition algorithm. > > > > > > > > If its new index is K, then on left side are top K integers. > If > > > > > index>K, > > > > > > > > apply algo on left side Else apply algo on right side. > > > > > > > > > > Best Case: O(1) > > > > > > > > Worst Case: O(n^2) > > > > > > > > > > But there are very less chances of worst case. It is when the > > > list is > > > > > > > > already sorted. > > > > > > > > > > On Thu, May 5, 2011 at 1:06 AM, amit < > amitjaspal...@gmail.com> > > > > > wrote: > > > > > > > > > Hi , > > > > > > > > > > > We are give a list of integers now our task is to find the > top > > > K > > > > > > > > > integers in the list based on frequency. > > > > > > > > > > > Apart from sorting the data can there be any other > algorithm? > > > > > > > > > > > -- > > > > > > > > > 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. > > > > > > > > > > -- > > > > > > > > Gaurav Aggarwal > > > > > > > > SCJP- Hide quoted text - > > > > > > > > > > - Show quoted text - > > > > > > > > > -- > > > > > > > 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.-Hidequoted text > - > > > > > > > > - Show quoted text - > > > > > > > -- > > > > > 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 > > > > > > Apoorve Mohan- Hide quoted text - > > > > > > - Show quoted text - > > > > > -- > > > 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.- Hide quoted text - > > > > - Show quoted text - > > -- > 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. > > -- PIYUSH SINHA 9936757773 -- 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.