The counting inversion can be done in O(n^2) with the naive algorithm.
But it will not suffice. So we need (nlogn). Counting the inversion in merge function of merge sort is good idea too do this. while merging if second array is having small element then the elements remaning in first array all have conflict with this element so add that and thats it.
or
create binary search tree ,step by step go on inserting the elememnts, and with every node keep track of nodes that are right side of current node and
while inserting increment the current nodes right count if inserted element falls to right (that is it is greater than current node element).and else if falls to left(that means inserted element is smaller than current node and there are right_count_of_current_node no of element greater than inserted element that are before inserted element so add that count) add right count to answer.
Solution with first strategy:
But it will not suffice. So we need (nlogn). Counting the inversion in merge function of merge sort is good idea too do this. while merging if second array is having small element then the elements remaning in first array all have conflict with this element so add that and thats it.
or
create binary search tree ,step by step go on inserting the elememnts, and with every node keep track of nodes that are right side of current node and
while inserting increment the current nodes right count if inserted element falls to right (that is it is greater than current node element).and else if falls to left(that means inserted element is smaller than current node and there are right_count_of_current_node no of element greater than inserted element that are before inserted element so add that count) add right count to answer.
Solution with first strategy:
No comments:
Post a Comment