An O(n) solution:
let a = [1,2..N]
print input[0] + 1
remove (input[0]+1) from a
for i = 1 to N-1
print a[input[i]]
remove a[input[i]] from a
On 5/7/07, Phanisekhar B V <[EMAIL PROTECTED]> wrote:
>
> 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
-~----------~----~----~----~------~----~------~--~---
