Hi, Given an inversion, how do i reconstruct the permutation in o(nlogn)
say suppose we have arr 1 2 3 4 5 inv 4 0 2 1 0 start from left, Step 1) arr[inv[0]]=5, step 2) arr 1 2 3 4 inv 0 2 1 0 arr[inv[0]]=arr[0]=1 Step 3) arr 2 3 4 inv 2 1 0 arr[inv[0]]= 4 Step 4) arr 2 3 arr 1 0 trivial 3 2 I want the updation of arr and inv automatically (within least time). Now once step i(say example step 2) is completed,i want arr to be updated automatically, especially the indices and the elements are to be removed. One slow way would be to write a for(i=k;i<n-1;i++) arr[i]=arr[i+1];(once kth element is deleted ). Is there any other way to solve this problem other than 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-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
