@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.- 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.
