@nivedita :hashing will not work if the range of nos is high On Sun, Jul 31, 2011 at 1:40 AM, nivedita arora <vivaciousnived...@gmail.com > wrote:
> ok lets think in terms of hashmap of number and frequency > we definitly have to maintain an order array . > traverse original array , we check if its present in hashmap ..if not > - 1)add it to hashmap and set frequency to 1 2)add it in order array > if yes then increment frequency by 1. > searching taking O(1) time . > > now traverse order array..search for corresponding freq and print > > this should take o(n) time...let me know if i faultered anywhere. > > @aditi- pls dont use just arrays..its not efficient way. > > On Jul 31, 12:51 am, rahul mittal <rahulmitta...@gmail.com> wrote: > > @nivedita:can u do this in o(n) time , i suppose your algorithm takes > > 0(nlogn) time > > > > On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora < > vivaciousnived...@gmail.com > > > > > > > > > > > > > > > > > > > > > wrote: > > > @rahul- balanced BST can be maintained.to remove worst case ! > > > @sukhmeet- i did not gt your method completely ..u are trying to > > > maintain hashmap or double dimension array of number and count? > > > @aditi- for array we will have overhead of searching if element is > > > present or not ..in O(n) time while it will be O(logn) in BST. > > > in array we cannot do binary search as it will not be sorted to > > > improve search . > > > > > On Jul 31, 12:31 am, rahul mittal <rahulmitta...@gmail.com> wrote: > > > > maintaining the bst of n element in worst case will take n square > time > > > > complexity ..do we have a better solution for worst case > > > > > > On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh < > sukhmeet2...@gmail.com > > > >wrote: > > > > > > > nivedita: wts the use to maintaining BST.. if the same purpose can > be > > > > > fulfilled by an array .. > > > > > but this can be a good method if the range of numbers is pretty > large.. > > > den > > > > > making a hash count can be difficult.. > > > > > > > On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora < > > > > > vivaciousnived...@gmail.com> wrote: > > > > > > >> take a BST whose node has an element of frequency .and another > array > > > > >> which will store order of elements. > > > > >> for each array element search BST if node already exists increase > the > > > > >> freq count ..other wise add that element in the order array we > took > > > > >> and insert new node in BST. > > > > > > >> now , scan the order array find its corresponding element in BST > and > > > > >> its frequency, print it that many times. > > > > > > >> let me know if there is any bttr method > > > > >> thx! > > > > > > >> On Jul 30, 11:58 pm, sukhmeet singh <sukhmeet2...@gmail.com> > wrote: > > > > >> > maintain a count array of all elements.. > > > > >> > now traverse the array again and the count array .. and build > the > > > new > > > > >> array > > > > > > >> > On Sun, Jul 31, 2011 at 12:24 AM, aditi garg < > > > aditi.garg.6...@gmail.com > > > > >> >wrote: > > > > > > >> > > Q1) Given an array with some repeating numbers. Like > 12,6,5,12,6 > > > > >> > > output: 12,12,6,6,5 > > > > > > >> > > 12 shud come before 6 since it is earlier in list. Please > provide > > > a > > > > >> > > gud algo fr dis > > > > > > >> > > -- > > > > >> > > 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. > > > > > > > -- > > > > > 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. > > > > > > -- > > > > *With Regards * > > > > *RAHUL MITTAL* > > > > *3rd YEAR* > > > > *CSE* > > > > *MNNIT ALLAHABAD* > > > > > -- > > > 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. > > > > -- > > *With Regards * > > *RAHUL MITTAL* > > *3rd YEAR* > > *CSE* > > *MNNIT ALLAHABAD* > > -- > 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, Kamakshi kamakshi...@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.
