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