数组中的逆序对 剑指offer java
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
思路：
1、看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)这个数字比较，因此这个算法的时间复杂度为O(n^2)。 （ 第一个数字要和n-1个比较，第二个和n-2个比较...倒数第二个要和最后一个比较，一共要比较num=1+2+3+...+(n-1)=O(n^2)；
2、考虑到归并排序的思想，
例如，两个已经排序的数组，假设按照从小到大排列的。例如下面的{5，7}和{4，6}，已经比较5>4,则不需要比较7和4了，可以减少至少一半的比较的次数。
(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；
在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图（c）所示， 避免在以后的统计过程中再重复统计。
合并子数组并统计逆序对的过程如下图如下图所示：
分别是:
1)初始tmp={0,0,0,0} ,n=2,(7与5，6和4两个逆序对）,i=0，mid=1,j=2 k=0
2）5与4比较，5>4, 执行 tmp[k++]=a[j++];, 所以tmp={4,0,0,0} 再执行 cnt+=mid-i+1; n=4 ,j=3 ,k=1
3)5与6比较，5<6, 执行 tmp[k++]=a[i++];所以tmp={4,5,0,0} ； i=1 ,mid不变,k=2
4）7与6比较，7>6,tmp[k++]=a[j++];, tmp={4,5,6,0},再执行 cnt+=mid-i+1; cnt=5 j=4,k=3
5) while(i<=mid)
tmp[k++]=a[i++]; 所以 tmp={4,5,6,7} k=4,i=2;
核心代码：
if(a[i]<=a[j]) tmp[k++]=a[i++]; else{ tmp[k++]=a[j++]; cnt+=mid-i+1; cnt%=1000000007; }
注意：main方法里面调用非静态方法时，需要new一个对象，因为静态方法，静态类属于模板，非静态类和方法属于对象
测试用例：
public static void main(String[] args) {
CompareTest1 com=new CompareTest1();
int []arr = {7,5,6,4};
int num=com.InversePairs(arr);System.out.println("逆序对的数目为"+ num);
}
修改这一部分代码，可以显示打印出逆序对：
最终输出结果如下图：
完整代码如下：
public class CompareTest1 {
int cnt;
public int InversePairs(int [] array) {
cnt=0;
if(array!=null)
mergeSortUpDown(array,0,array.length-1);
return cnt;
}
/*
* 归并排序(从上往下)
*/
public void mergeSortUpDown(int[] a, int start, int end){
if(start>=end)
return ;
int mid=(start+end)/2;
mergeSortUpDown(a,start,mid);
mergeSortUpDown(a,mid+1,end);
merge(a,start,mid,end);
}
/*
* 将一个数组中的两个相邻有序区间合并成一个
*/
public void merge(int[] a, int start, int mid, int end) {
int[] tmp=new int[end-start+1];
int i =start,j=mid+1,k=0;
while(i<=mid&&j<=end){
if(a[i]<=a[j])
tmp[k++]=a[i++];
else{
tmp[k++]=a[j++];
cnt+=mid-i+1;
cnt%=1000000007;//需要对cnt进行1000000007取模。不然逆序对数目会溢出
}
}
while(i<=mid)
tmp[k++]=a[i++];
while(j<=end)
tmp[k++]=a[j++];
for(k=0;k<tmp.length;k++){
a[start+k]=tmp[k];
}
}
public static void main(String[] args) {
CompareTest1 com=new CompareTest1();
int []arr = {7,5,6,4};
int num=com.InversePairs(arr);
System.out.println(num);
}
}
参考：Aurora1