One approach will be while creating a BST and also store position of the element in the original array. While constructing ar_low check for two condition 1. element should be less than the given element and also position of element should greater than the given element.
On Tue, Jul 13, 2010 at 4:01 AM, Vipul Agrawal <[email protected]>wrote: > // sort ar[] > and store in temp[] -- o(nlogn) > > for(i=0 to n-1) > { > //search position of ar[i] in temp[] binary search --o(logn) > ar_low[i] = pos-1; > delete temp[pos]; > } > > > in binary search increase pos until next element is same . > > > > On Tue, Jul 13, 2010 at 4:09 PM, Amir hossein Shahriari < > [email protected]> wrote: > >> make a balanced bst which also has the size of subtree at each node >> start from ar[n-1] and insert each element and see what is it's rank in >> BST >> for finding the rank when inserting each time you pick the right subtree >> add size of left subtree to rank >> O(nlogn) >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
