@Anand Depending upon the sequence of data in the input, an insertion/search into the (unbalanced) BST will take O(n) time causing the overall complexity to shoot up to O(n^2) for each element counted once. Sourav's approach requires a balanced binary search tree.
@Divya.. If you know something about the numbers, one could do better. For example, if you knew that they're all positive short integers, Anand's original approach (of using an array indexed by the numbers themselves) will be great (for a storage cost of about 64KB). This is sometimes more acceptable, for example, if your original input is like a million integers. On Tue, Jun 8, 2010 at 5:48 AM, Anand <anandut2...@gmail.com> wrote: > @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<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.
