Here is an algorithm which solves this problem in O(nlog^2 n):
Create a set of pairs B= {<ar [i],i >: i= 1..n}.
Sort B.
Now use the following Divide and Conquer algorithm (Ar_Low is a global
array):
Fill (Start, End, Low_Array)
if Start= End then
Low_Array [Start]= 0
else
Initialize Low_Array with zero.
Fill (Start, (Start+ End)/ 2, Low_Array)
Fill ((Start+ End)/ 2+ 1, End, Low_Array)
Scan B (the list of sorted pairs) and select the pairs whose
second value is in range (End/ 2+ 1, End), call the resulting list B'
For each i in (Start, (Start+ End)/ 2):
Lets j be the position of arr [i] in B'
Set Low_Array [i]= Low_Array [i]+ j
The running time of this algorithm is:
n\log n for sorting B+
T(n)= 2T(n/2)+ n\log n => T(n)= n\log^2 n
So, the total running time is: n\log^2 n .
Amir
On 07/26/2011 06:48 AM, Piyush Sinha wrote:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.
--
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.
