I feel its possible to do it in O(n log n) for randomized input. I tried for
small input (input with 10 numbers), and i have a feeling that it will work
for input n.
Although the worst case might turn out to be O(n^2).
On 5/4/07, Karthik Rathinavelu <[EMAIL PROTECTED]> wrote:
>
> Assuming that 'n' is passed along the function
>
> Pseudocode 1: O(n*n)
> construct_array (int *a, int n, int *output)
> {
> construct_linkedlist(1 ... n);
> Node *current = list->head;
> int i=0, j=0;
> int tvar;
> for(i=0;i<n;i++) {
> if(a[i] == 0) {
> output[j++] = list->head->data;
> delete_head(llist);
> } else {
> for(tvar=a[i];tvar>1;tvar--)
> current = current->next;
> output[j++] = current->next->data;
> remove_next(llist, current);
> }
> current = list->head;
> }
> }
>
> Pseudocode 2: O(n*n)
>
> construct_array(int *a, int n, int *output)
> {
> int i = 0, j = 0;
> int op = 1;
> while(op <= n) {
> while(a[i++])
> ;
> output[i] = op;
> a[i] = -1;
> for(j=0;j<i;j++)
> a[j]--;
> op++;
> i = 0;
> }
> }
>
> Algo 3: O(n*n)
>
> construct a stack with no. from 1...n in it.
>
> Read the input array pop that many elements and the stack top is the
> current position in the output array. delete stack top after storing it in
> the output array
>
> push back the popped elements back
>
> I am not sure whether an O(n) solution possible for this ...chk it out
> anyway
>
> On 5/4/07, 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.
> >
> >
> >
> >
> >
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
