We can use following logic : -
1- create a copy of original array A - O(n)
2- sort the original array using randomised quick sort - O(n log n)
3 - iterate in copy array B from left and for every element in B
find its position in A using binary search
distance = position of B[i] in A) - i;
inversion_count += ( distance>0 ? distance : 0 );
Time complexity - O(n) + O(n log n) + O (n log n) => O(n log n)
On Saturday, 14 May 2011 18:50:41 UTC+5:30, WgpShashank wrote:
>
> @all i have posted the solution of same problem few times back ,
> search in group thread
> i used BST & using that inversion count can be calculated in O(nlogn)
> if you found any error on that then let me know
>
>
> Thanks
> Shashank
> CSE,BIT Mesra
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/Yk_WG2yst24J.
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.
