On May 4, 6:33 am, Abhi <[EMAIL PROTECTED]> wrote:
> You are given an array of n numbers and each element is equal to the
> count of numbers less than that number in right hand side of the
> original and we have to find the original array;
> It is given that the n-numbers in the original array is from 1 to n.
>
> For ex. if the original array is 4,1,3,2
> Then we would we given the array 3,0,1,0
> Ex no 2. Original array 2,3,1,4
> Given array 1,1,0,0
> Ex no. 3 original array 5, 2,1,3,4
> Given array 4, 1,0,0,0
>
> Can any one suggest space and time efficient solution for this.
Let c[1..n] be the array of counts.
Let a[1..n] be the array to contain the solution, where
1 <= a[i] <= n and a[i] = a[j] iff i = j.
Let T be an (initally empty) AVL tree whose elements are
numbers, and were each node contains a count of the
number of elements in the subtree for with the node
is the root. (In such a tree, insertion time is still O(log n),
and finding the number of nodes whose key is less
than or equal to a given key value has time O(log n). )
for i := 1 to n
{
a[i] := c[i] + 1;
a[i] := a[i] + (number of nodes in T whose key <= a[i]);
insert a[i] into T;
}
Time complexity is O(n * log n).
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
