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