剑指Offer:数组逆序对

题目

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。例如,在数组{7,5,6,4}中,一共存在5个逆序对(7,6),(7,5),(7,4),(6,4),(5,4)输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
题目保证输入的数组中没有的相同的数字

数据范围:
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

分析

我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每扫描到一个数字的时候,我们不能拿它和后面的所有数字比较否则时间复杂度就是O(n^2),因此我们可以考虑先比较两个相邻的数字。

IMG_20180520_100738.jpg

我们先将数组分解成两个长度为2的子数组,再把这两个子数组分别拆分成两个长度为1的子数组。接下来一边合并相邻的子数组,一边统计逆序对的数目。在第一对长度为1的子数组{7},{5}中7大于5因此(7,5)组成一个逆序对。同样的(6,4)组成一个逆序对。由于已经统计了这两个子数组内部的逆序对,因此只需要把这两对子数组排序。以免重复统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Solution {
public int InversePairsCore(int[] array, int[] copy, int low, int high) {
if(low==high)
{
return 0;
}
int mid = (low+high)>>1;
int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
int count = 0;
int i=mid;
int j=high;
int locCopy = high;
while(i>=low&&j>mid)
{
if(array[i]>array[j])
{
count += j-mid;
copy[locCopy--] = array[i--];
if(count>=1000000007)//数值过大求余
{
count%=1000000007;
}
}
else
{
copy[locCopy--] = array[j--];
}
}
for(;i>=low;i--)
{
copy[locCopy--]=array[i];
}
for(;j>mid;j--)
{
copy[locCopy--]=array[j];
}
for(int s=low;s<=high;s++)
{
array[s] = copy[s];
}
return (leftCount+rightCount+count)%1000000007;
}
public int InversePairs(int [] array) {
int length = array.length;
if (length == 0)
return 0;
int[] copy = new int[length];
for (int i = 0; i < length; i ++) {
copy[i] = array[i];
}
return InversePairsCore(array, copy, 0, length-1);
}
}