Count inversions (merge sort)
Java
Hard
5 views
Problem Description
Task: return number of inversions in array using merge sort.
Output Format
Return value
Constraints
Use long; O(n log n).
Official Solution
static long inversions(int[] a){int[] tmp=new int[a.length];return ms(a,tmp,0,a.length-1);}static long ms(int[] a,int[] t,int l,int r){if(l>=r) return 0;int m=(l+r)/2;long c=ms(a,t,l,m)+ms(a,t,m+1,r);int i=l,j=m+1,k=l;while(i<=m&&j<=r){if(a[i]<=a[j]) t[k++]=a[i++];else{t[k++]=a[j++];c+=m-i+1;}}while(i<=m) t[k++]=a[i++];while(j<=r) t[k++]=a[j++];for(i=l;i<=r;i++) a[i]=t[i];return c;}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!