@souravsain :Your approach works really well.. Here is the Implementation: http://codepad.org/ricAcQtu
On Sun, Jun 6, 2010 at 11:40 AM, souravsain <souravs...@gmail.com> wrote: > @divya:go through the elements and keep inserting them in a BST. While > inserting if elements already exists in BST, increase its frequency > (Node of BST has element a nd frequency). Also if elemengs is newly > inserted then also place it in a seperate array. So this array (say > Array M) will become something like 12,5,6. This array will give order > of first occurance of numbers. This whole process will take nlogn (BST > creation assuming worst case that all elements are uinque in the input > array). > > Once done, scan through each element in array M, find its > corrosponding element in BST (logn) which will give the frequency. > Fill those many indexes in input array with array M[i]. If all > elements are uinque, this will also take nlogn. Else if input array > has m distince elements, which will require us to look into BST for m > times. > > hence entire process has time compelxity: O(nlogn + nlogn)= O(2nlogn) > Space complexity: O(2n) [1 for BST and 1 for array M, worst case when > all elements are unique in inpur array). > > Let me know your comments if any or any better appraoch as this once > may have improvements. > > On Jun 6, 7:47 pm, divya jain <sweetdivya....@gmail.com> wrote: > > output willl be 12 12 5 6 6 > > > > On 6 June 2010 18:27, souravsain <souravs...@gmail.com> wrote: > > > > > > > > > @divya: Does your problem require the output to be sorted also? What > > > will be the output required if inout is 12,5,6,12,6? Will it be > > > 12,12,6,6,5 or 12,12,5,6,6,? > > > > > Sain > > > > > On Jun 6, 12:01 am, divya <sweetdivya....@gmail.com> wrote: > > > > 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. So cant use a > > > > dictionary > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
