We can use "count sort" to solve this. Assuming each element is the array is in range 1-k (k=O(n)).
for (i=0 to n) C[A[i]]=C[A[i]]+1 for (i=1 to k) C[i]=C[i]+C[i-1] Array 'C' will have the resultant array. On Jul 26, 9:20 pm, Rajeev Kumar <[email protected]> wrote: > * > Algorithm : > 1)Conside original array a[] > 2)Construct a sorted list with the array elements(O(nlogn)) > 3)Traverse across all elements of the original array 'a' and find it's > position(right occurence) in the sorted list using binary search. > -position in the sorted list returns the number of elements in the less > than the current element on right side. > -after remove the current element from the sorted list. > PS: list is preferred datastructure because there are so many insertion and > deletion operations. > > check this link > :http://rajeevprasanna.blogspot.com/2011/07/count-number-of-min-elemen... > * > On Tue, Jul 26, 2011 at 11:08 AM, ankit sambyal <[email protected]>wrote: > > > @vivin : Your algo seems to be wrong. Plz take an example and > > explain. I may hv misunderstood u .. > > > -- > > 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. > > -- > Thank You > Rajeev Kumar -- 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.
