//利用归并排序来完成，归并排序可参考前面代码，归并排序可用来完成这类逆序对之类的问题，采用分治的思想，对于归并排序的代码不需要多改动，只需要在归并之前进行一次寻找操作，找出count的数量
class Solution { private int count=0; public int reversePairs(int[] nums) { if(nums == null || nums != null && nums.length == 0) return 0; mergeSort(nums,0,nums.length-1); return count; } public void mergeSort(int[] arr,int l,int r) { if(l>=r) return ; int mid=(l+r)/2; mergeSort(arr,l,mid); mergeSort(arr,mid+1,r); merge(arr,l,mid,r); } public void merge(int[] arr,int l,int mid,int r) { int[] aux=new int[r-l+1]; for(int i=l;i<=r;i++) { aux[i-l]=arr[i]; }
//这几行代码就是寻找count的操作了，可以重新写个函数来完成这部分
//本人之前的错误一直是想要在归并的时候来进行判断count的数量，也就是在后面的for循环中比较两个数的值时，比如说第一个 i 指向的那个元素与右边 j 指向的那个元素比较时，还要多判断一下是否是两倍的大小，非常不容易写，我也一直没写出来，后来参考了一下别人的归并过程才发现，这部分完全可以独立出来写 int i=l,j=mid+1; while(i<=mid&&j<=r) { long x=arr[i]; long y=2*(long)arr[j]; if(x>y) { count+=mid-i+1; j++; } else{ i++; } } i=l; j=mid+1; for(int k=l;k<=r;k++) { if(i>mid) { arr[k]=aux[j-l]; j++; } else if(j>r) { arr[k]=aux[i-l]; i++; } else if(aux[i-l]<aux[j-l]) { arr[k]=aux[i-l]; i++; } else { arr[k]=aux[j-l]; j++; } } }}
转载于:https://www.cnblogs.com/cold-windy/p/11195398.html
