On Mon, May 9, 2011 at 11:44 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 > 3rd largest element based on frequency should be 3 i think? > 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. >> >> > -- > 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. > -- Aamir Khan Indian Institute of Technology Roorkee, Roorkee, Uttarakhand, India , 247667 Phone: +91 9557647357 email: aami...@iitr.ernet.in <aamir...@iitr.ernet.in> ak4u2...@gmail.com -- 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.
