数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007

输入描述:

题目保证输入的数组中没有的相同的数字

数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

示例1

输入

1,2,3,4,5,6,7,0

输出

　　7

题目链接

法一（借鉴）：o(nlgn)。这题很容易想到的是o(n^2)的解决办法，就不说了，超时。利用归并分治的思想，将数组分成两部分，先分别计算左段和右段的逆序对（计算完成后就会变成有序的，这是归并排序中的分解），
再计算左段+右段的逆序对（这是归并排序中的归并，分别对两个数组从后往前进行遍历，如果第一个数组的末尾数值大于第二个的末尾数值，则此时可以有第二个数组长度那么多的逆序对存在，此时将大数移到临时数组中，
再继续进行遍历，重复进行）。代码如下（耗时700ms）：

 1 public int InversePairs(int [] array) {
 2         int len = array.length;
 3         int[] tmp = new int[len];
 4         long res = InversePairsCore(array, 0, len - 1, tmp);
 5         return (int)(res % 1000000007);
 6     }
 7     public static long InversePairsCore(int[] array, int left, int right, int[] tmp) {
 8         long inver = 0;
 9         if(left < right) {
10             int mid = (left + right) / 2;
11             inver += InversePairsCore(array, left, mid, tmp);//找左半段的逆序对数目
12             inver += InversePairsCore(array, mid + 1, right, tmp);//找右半段的逆序对数目
13             inver += MergeArray(array, left, mid, right, tmp);//在找完左右半段逆序对以后两段数组有序，然后找两段之间的逆序对。最小的逆序段只有一个元素。
14         }
15         return inver;
16     }
17     public static long MergeArray(int[] array, int left, int mid, int right, int[] tmp) {
18         //i是左半段末尾下标，j是右半段末尾下标，k是临时数组末尾下标
19         int i = mid, j = right, k = 0;
20         long cnt = 0;
21         //设定两个指针ij分别指向两段有序数组的末尾元素，将大的那一个放入到临时数组中去。
22         while(i >= left && j > mid) {
23             if(array[i] > array[j]) {
24                 tmp[k++] = array[i--];//从临时数组的最后一个位置开始排序
25                 cnt += j - mid;//因为arry[mid+1...j...end]是有序的，如果arry[i]>arry[j]，那么也大于arry[j]之前的元素，从a[mid+1...j]一共有j-(mid+1)+1=j-mid
26             }
27             else {
28                 tmp[k++] = array[j--];
29             }
30         }
31         //表示前半段数组中还有元素未放入临时数组
32         while(i >= left) {
33             tmp[k++] = array[i--];
34         }
35         while(j > mid) {
36             tmp[k++] = array[j--];
37         }
38         //将临时数组中的元素写回到原数组当中去。
39         for(i = 0; i < k; i++) {
40             array[right - i] = tmp[i];
41         }
42         return cnt;
43     }

View Code

法二（剑指offer标准）：与上面的解法逻辑相同，只是代码方式不同。代码如下：

 1 public int InversePairs(int [] array) {
 2         int len = array.length;
 3         int[] tmp = new int[len];
 4         int res = InversePairsCore(array, 0, len - 1, tmp);
 5         return res;
 6     }
 7     private static int InversePairsCore(int[] array, int left, int right, int[] tmp) {
 8         if(left == right) {
 9             return 0;
10         }
11         int mid = (left + right) >> 1;
12         //统计左半段的逆序对
13         int leftCnt = InversePairsCore(array, left, mid, tmp) % 1000000007;
14         //统计右半段的逆序对
15         int rightCnt = InversePairsCore(array, mid + 1, right, tmp) % 1000000007;
16         //统计左半段+右半段的逆序对
17         int cnt = 0;
18         //标记左半段末尾下标
19         int i = mid;
20         //标记右半段末尾下标
21         int j = right;
22         //临时数组末尾下标
23         int k = right;
24         while(i >= left && j > mid) {
25             if(array[i] > array[j]) {
26                 cnt += j - mid;
27                 tmp[k--] = array[i--];
28                 if(cnt >= 1000000007) {
29                     cnt %= 1000000007;
30                 }
31             }
32             else {
33                 tmp[k--] = array[j--];
34             }
35         }
36         while(i >= left) {
37             tmp[k--] = array[i--];
38         }
39         while(j > mid) {
40             tmp[k--] = array[j--];
41         }
42         for(i = left; i <= right; i++) {
43             array[i] = tmp[i];
44         }
45         return (leftCnt + rightCnt + cnt) % 1000000007;
46     }

View Code