题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
/** * */ package 数组; /** * <p> * Title:InversePairs * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月14日 上午9:39:02 */ public class InversePairs { /** * @param args */ public int IntInversePairs(int[] array) { if (array == null || array.length == 0) { return 0; } int[] copy = new int[array.length]; // 辅助存储空间，里面的内容和array的是一样的.数组副本，用于归并排序 /*for (int i = 0; i < array.length; i++) { copy[i] = array[i]; }*/ int count = InversePairsCore(array, copy, 0, array.length - 1);// 数值过大求余 return count; } public int InversePairsCore(int[] array, int[] copy, int low, int high) { // 递归终止条件 if (low >= high) { return 0; } // 递归 int mid = (low + high) / 2; int leftCount = InversePairsCore(array, copy, low, mid) % 1000000007; int rightCount = InversePairsCore(array, copy, mid + 1, high) % 1000000007; // 核心部分，合并放入拷贝数组和进行逆序统计 int count = 0; int left = mid; int right = high; int copyindex = high; // 合并子数组，并且统计逆序次数 while (left >= low && right > mid) { if (array[left] > array[right]) { count += right - mid; copy[copyindex--] = array[left--]; if (count >= 1000000007)// 数值过大求余 { count %= 1000000007; } } else { copy[copyindex--] = array[right--]; } } // 比较两个已排好序的子数组，如果左边子数组的值大于右边的，说明逆序，次数为右边子数组的长度 // 跳出循环的条件是，其中一个子数组已经全部放入了辅助数组空间，接下来把剩下子数组的数全部填充进去。 for (; left >= low; left--) { // 右边子数组放置完毕 copy[copyindex--] = array[left]; } for (; right > mid; right--) { // 左边子数组放置完毕 copy[copyindex--] = array[right]; } for (int s = low; s <= high; s++) { //统计好并且排好序后放入原数组，将原数组返回给上一层继续重复操作 array[s] = copy[s]; } return (leftCount + rightCount + count) % 1000000007; } public static void main(String[] args) { int[] array = { 1, 2, 3, 4, 5, 6, 7, 0 }; InversePairs inv = new InversePairs(); System.out.println(inv.IntInversePairs(array)); for (int i = 0; i < array.length; i++) { System.out.print(array[i]); } } }
