题目描述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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
算法解析： 这个时候，最直观的解法必然是用顺序扫描，但是往往最直观的不是最好的，我们这里举个栗子：数组[7, 5, 6, 4， 3， 2， 4， 1]， 我们先考虑两个相邻的数字是否是逆序对，比如[7, 5], [6, 4], [3, 2], [4, 1], 这4个子数组，我们对其进行判定后，合并排序，同时统计逆序，然后形成四个子数组为[5, 7], [4, 6], [2, 3], [1, 4],这时候因为我们是顺序分解的子数组，所以两个子数组之间同样要统计逆序，比如[5, 7] 和[4, 6]，[2, 3] 和[1, 4]，因为逆序对，是前一个数字比后边的数字大形成逆序对，而现在的子数组又是从小到大有序的，那么就可以将遍历起点放到两个子数组的末尾，如果前一个子数组的末尾比后一个子数组的末尾大，则代表前一个数组的末尾数字对后边的子数组的每一个数字都形成逆序对。如果前一个子数组的遍历指针指向的值比后边子数组遍历指针指向的值小，则代表可能含有逆序对，但是需要在后一个子数组中向前查找，当然最后需要修改数组的值，不然会发生重复统计的问题。这个过程就类似归并排序。 代码如下：
public static int InversePairs(int [] array) { if (array == null || array.length <= 1){ return 0; } int[] temp = new int[array.length]; int count = mergeSort(temp, array, 0, array.length - 1); return (count % 1000000007); } PRivate static int mergeSort(int[] temp, int[] array, int start, int end) { if (start >= end){ return 0; } int mid = (start + end) >> 1; int leftCount = mergeSort(temp, array, start, mid)%1000000007; int rightCount = mergeSort(temp, array, mid + 1, end)%1000000007; int count = 0; int leftP = mid; int rightP = end; int copyP = end; while (leftP >= start && rightP > mid){ if (array[leftP] > array[rightP]){ count += rightP - mid; temp[copyP --] = array[leftP --]; if (count >= 1000000007){ count %= 1000000007; } }else{ temp[copyP --] = array[rightP --]; } } for (; leftP >= start; leftP--) { temp[copyP --] = array[leftP]; } for (; rightP > mid; rightP--) { temp[copyP --] = array[rightP]; } for (int i = start; i <= end; i++) { array[i] = temp[i]; } return (leftCount + rightCount + count) % 1000000007; }新闻热点
疑难解答
