在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
public int InversePairs(int [] arr) { if(arr == null || arr.length <= 1){ return 0; } return mergeSort(arr, 0, arr.length - 1).pairs;}
借助归并排序的流程,将归并流程中前一个数组的数比后一个数组的数小的情况记录下来。
归并的原始逻辑是根据输入的无序数组返回一个新建的排好序的数组:
public int[] mergeSort(int[] arr, int start, int end){ if(arr == null || arr.length == 0 || start < 0 || end > arr.length - 1 || start > end){ throw new IllegalArgumentException(); } if(start == end){ return new int[]{ arr[end] }; }
int[] arr1 = mergeSort(arr, start, mid); int[] arr2 = Info right = mergeSort(arr, mid + 1, end); int[] copy = new int[arr1.length + arr2.length]; int p1 = 0, p2 = 0, p = 0;
while(p1 < arr1.length && p2 < arr2.length){ if(arr1[p1] > arr2[p2]){ copy[p++] = arr1[p1++]; }else{ copy[p++] = arr2[p2++]; } } while(p1 < arr1.length){ copy[p++] = arr1[p1++]; } while(p2 < arr2.length){ copy[p++] = arr2[p2++]; } return copy;}
而我们需要再此基础上对子状态收集的信息进行改造,假设左右两半部分分别有序了,那么进行 merge
的时候,不应是从前往后复制了,这样当 arr1[p1]>arr2[p2]
的时候并不知道 arr2
的 p2
后面还有多少元素是比 arr1[p1]
小的,要想一次比较就统计出 arr2
中所有比 arr1[p1]
小的数需要将 p1,p2
从 arr1,arr2
的尾往前遍历:
而将比较后较大的数移入辅助数组的逻辑还是一样。这样当前递归状态需要收集左半子数组和右半子数组的变成有序过程中记录的逆序对数和自己 merge
记录的逆序对数之和就是当前状态要返回的信息,并且 merge
后形成的有序辅助数组也要返回。
public int InversePairs(int [] arr) { if(arr == null || arr.length <= 1){ return 0; } return mergeSort(arr, 0, arr.length - 1).pairs;}
class Info{ int arr[]; int pairs; Info(int[] arr, int pairs){ this.arr = arr; this.pairs = pairs; }}
public Info mergeSort(int[] arr, int start, int end){ if(arr == null || arr.length == 0 || start < 0 || end > arr.length - 1 || start > end){ throw new IllegalArgumentException(); } if(start == end){ return new Info(new int[]{arr[end]}, 0); }
int pairs = 0; int mid = start + ((end - start) >> 1); Info left = mergeSort(arr, start, mid); Info right = mergeSort(arr, mid + 1, end); pairs += (left.pairs + right.pairs) % 1000000007;
int[] arr1 = left.arr, arr2 = right.arr, copy = new int[arr1.length + arr2.length]; int p1 = arr1.length - 1, p2 = arr2.length - 1, p = copy.length - 1;
while(p1 >= 0 && p2 >= 0){ if(arr1[p1] > arr2[p2]){ pairs += (p2 + 1); pairs %= 1000000007; copy[p--] = arr1[p1--]; }else{ copy[p--] = arr2[p2--]; } }
while(p1 >= 0){ copy[p--] = arr1[p1--]; } while(p2 >= 0){ copy[p--] = arr2[p2--]; }
return new Info(copy, pairs % 1000000007);}
出自:http://www.zhenganwen.top
已获授权
END