题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数 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 public class Solution { 2 private int cnt; 3 private void MergeSort(int[] array, int start, int end){ 4 if(start >= end) return; 5 int mid = (start + end) / 2; 6 MergeSort(array, start, mid); 7 MergeSort(array, mid+1, end); 8 MergeOne(array, start, mid, end); 9 } 10 private void MergeOne(int[] array, int start, int mid, int end){ 11 int[] temp = new int[end - start + 1]; 12 int k = 0, i = start, j = mid + 1; 13 while(i <= mid && j <= end){ 14 //如果前面的元素小于后面的不能构成逆序对 15 if(array[i] <= array[j]) 16 temp[k++] = array[i++]; 17 else{ 18 //如果前面的元素大于后面的，那么在前面元素之后的元素都能和后面的元素构成逆序对 19 temp[k++] = array[j++]; 20 cnt = (cnt + (mid-i+1)) % 1000000007; 21 } 22 } 23 while(i <= mid) 24 temp[k++] = array[i++]; 25 while(j <= end) 26 temp[k++] = array[j++]; 27 for(int l = 0; l < k; l++){ 28 array[start+l] = temp[l]; 29 } 30 } 31 public int InversePairs(int [] array) { 32 MergeSort(array, 0, array.length-1); 33 return cnt; 34 } 35 }
原文：https://www.cnblogs.com/lf6688/p/13655774.html