@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> > > . > > 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
