题目形容
在数组中的两个数字，假如前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入形容
题目保证输入的数组中没有的相同的数字数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5示例
输入1,2,3,4,5,6,7,0输出7思路
1.可以通过移动数字发现，计算逆序对的方式和归并排序的merge操作有类似之处。
2.当进行merge操作时，若左边数组的元素大于右边数组的某一元素时，说明存在mid-left-l个逆序对。
- 由于左边数组和右边数组都是排好序的
- l索引代表左边数组当前索引
- 可以参照下图，了解归并过程中的计算逻辑。
Java代码实现
public class Solution { private int count = 0; public int InversePairs(int [] array) { if(array != null){ mergeSort(array,0,array.length-1); } return count; } private void mergeSort(int[] array,int left,int right){ if(left >= right){ return ; } int mid = (left + right)/2; mergeSort(array,left,mid); mergeSort(array,mid+1,right); merge(array,left,mid+1,right); } private void merge(int[] array,int left,int mid,int right){ int[] leftArray = new int[mid-left]; int[] rightArray = new int[right-mid+1]; for(int i=left;i<mid;i++){ leftArray[i-left] = array[i]; } for(int i=mid;i<=right;i++){ rightArray[i-mid] = array[i]; } int l = 0; int r = 0; int k = left; while(l < leftArray.length && r < rightArray.length){ if(leftArray[l] > rightArray[r]){ array[k++] = rightArray[r++]; count = (count + mid - left- l)%1000000007; }else{ array[k++] = leftArray[l++]; } } while(l < leftArray.length){ array[k++] = leftArray[l++]; } while(r < rightArray.length){ array[k++] = rightArray[r++]; } }}Golang代码实现
var res int = 0func InversePairs(nums []int) int { mergeOuter(nums,0,len(nums)-1) return res}func mergeOuter(nums[] int,left int,right int){ if left >= right{ return } mid := (left + right)/2 mergeOuter(nums,left,mid) mergeOuter(nums,mid+1,right) merge(nums,left,mid+1,right)}func merge(nums []int,left int,mid int,right int){ leftArray := make([]int,mid-left) rightArray := make([]int,right-mid+1) for i:=left; i<mid;i++{ leftArray[i-left] = nums[i]; } for i:=mid; i<=right;i++ { rightArray[i-mid] = nums[i]; } k := left l,r := 0,0 for l<len(leftArray) && r<len(rightArray) { if leftArray[l] > rightArray[r]{ nums[k] = rightArray[r] k++ r++ res = (res + mid - left - l)%1000000007 }else{ nums[k] = leftArray[l] k++ l++ } } for l<len(leftArray) { nums[k] = leftArray[l] k++ l++ } for r<len(rightArray){ nums[k] = rightArray[r] k++ r++ }}
