【解题思路】在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P00000007
【输入描述】题目保证输入的数组中没有的相同的数字 数据范围： 对于P的数据,size<=10^4 对于u的数据,size<=10^5 对于0的数据,size<=2*10^5
【输入样例】 1,2,3,4,5,6,7,0
【输出样例】 7
注：从题目描述来看，测试数据会非常大，单纯的暴力循环会超时
【解题思路】 //1. 利用二路归并排序的思想。 //2. 在二路归并排序中，若左子区间的某个数a[i]>a[j]右子区间的某个数，则从a[i~center]都是大于a[j]的，所以逆序数也就等于count +=center-i+1,这里center为左子区间的最后一个值的下标。
public class Solution { private long count; public int InversePairs(int [] array) { if(array==null || array.length==0){ return 0; } count = 0; mergeSort(array, 0, array.length-1); int c = new Long(count%1000000007).intValue(); return c; } public void mergeSort(int[] input, int left, int right){ int mid = (left + right) / 2; if (left < right) { // 左边 mergeSort(input,left,mid); // 右边 mergeSort(input,mid+1,right); // 左右归并 sort(input,left,mid,right); } } public void sort(int[] input, int left, int center, int right){ int []tempArray = new int[right-left+1]; int mid = center+1; int temp = left; int current = 0; while(left<=center && mid<=right){ if(input[left]>input[mid]){ tempArray[current++]=input[mid++]; count +=center-left+1; }else{ tempArray[current++]=input[left++]; } } //只会执行一个 while(left<=center){ tempArray[current++]=input[left++]; } while(mid<=right){ tempArray[current++]=input[mid++]; } current=0; while(temp<=right){ input[temp++]=tempArray[current++]; } } }