本文共 4906 字,大约阅读时间需要 16 分钟。
题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有相同的数字
数据范围:
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
思路:
方法1:遍历数组,每遍历一个元素在遍历这个元素后面的元素,时间复杂度为O(n^2)
方法2:归并排序的思想(归并排序利用的是分治的思想,由拆分和合并两个步骤组成,拆分和合并都需要递归调用来实现)
即先将数组不断的分割成两个部分,通过递归不断的分成两个部分,直到最后每一半只有1个元素为止停止递归,显然对于当个元素来说,其逆序对为0,然后逐一进行合并,7和5合并时由于left、right子数组内部的逆序对都是0,因此只要计算合并时产生的逆序对数目即可,同时要求合并后的数组排序,排序后在内部就没有逆序对了,从而不会对后续的逆序对寻找差生影响,同时排序后对于合并时确定逆序对的数目很方便(这也是归并排序中的做法,先二分再合并,共要进行logn次合并,每次合并时要进行排序,排序要遍历两个子数组并记录较小值从而需要消耗时间复杂度O(n)以及空间复杂度O(n),从而归并排序的时间复杂度是O(nlogn),空间复杂度为O(n)。本题中空间复杂度为O(n),归并排序优化后可以做到空间复杂度为O(1))。
每次合并merge方法中如何计算有多少逆序对?
已知左右两个子数组left,right是有序的,设置两个指针,分别在左右两个数组的第一个元素leftPoint、rightPoint上面,比较两个数值大小,如果leftPoint<rightPoint,表示这两个数不构成逆序对,于是将leftPoint++,再次比较;如果leftPoint> rightPoint,说明这是一个逆序对,并且leftPoint后面的数都比leftPoint要大,所以与rightPoint都可以构成逆序对,所以由leftPoint产生的逆序对数目是leftPoint数组中leftPoint以及后面元素的数目即middle-leftPoint+1;然后将rightPoint++再次比较leftPoint和rightPoint。当left、right两个数组遍历完成后就可以知道在合并过程中产生的逆序对的数目;在leftPoint和rightPoint的比较过程中,除了计算逆序对数目之外还要对合并后的数组排序,排序在leftPoint和rightPoint逐一比较的过程中进行,每次leftPoint和rightPoint比较,将较小的值放入到创建的temp[]数组上面,如果left或者right一侧的数组提前遍历完成,呢么逆序对不再增加,将right或者left数组中剩下的元素全部直接复制到temp[]中即可;最终当left和right数组遍历合完成后这个数组对应在temp中就是有序的,由于下一次合并在array[]数组基础上进行而不是在temp基础上进行,因此需要将temp[]从start到end的部分重新对array进行覆盖。
理解:归并排序分成“分”和“并”两个部分,分别用divide()方法和merge()方法来实现功能,其中divide()方法是递归方法,merge()方法不是递归方法,因此在divide()方法中需要有终止递归循环的边界条件,同时在divide()方法中要调用自身divide()方法和merge()方法实现下一层子数组的拆分和合并,即在divide()方法里面除了递归调用自身方法进行进一步的分割之外还要调用merge方法对分割后的子数组进行合并。在主函数中,只要给定初始边界条件,然后直接调用divide()方法即可解决问题,当然也可以在主函数中先自己分割一次得到left数组和right数组,在对两个数组递归调用divide方法再进行合并,但是这没有必要,可以省略,如程序所示。此外还要注意取模不仅要在返回结果时取模还要在程序中用到count的地方都是用取模,避免溢出。
// 找逆序对较复杂,这里使用分治思想,利用归并排序来找逆序对,就是在归并排序的基础上,在每次合并时对逆序对进行了统计而已,关键还是熟练使用递归。
public class Solution { //定义一个成员变量用来统计逆序对的数目 int count; public int InversePairs(int [] array) { //特殊输入和边界输入 if(array==null||array.length<=0) return 0; //使用递归方法不断进行拆分和合并 //创建一个数组用来在合并时存储排序后的数 int tempArray[]=new int[array.length]; int middle=(0+array.length-1)/2; //对左数组进行拆分合并得到左数组的逆序对数目 this.divide(array,tempArray,0,array.length-1); //①对右数组进行拆分合并得到右数组的逆序对数目,注意这里①②不需要写,直接写divide就可以 //this.divide(array,tempArray,middle+1,array.length-1); //②对左右两个数组进行合并计算合并时产生的逆序对数目 //this.merge(array,tempArray,0,array.length-1); //count在方法调用的过程中不断增长,方法结束时count就是结果,将其返回即可 return count%1000000007; } //这个方法用来将数组进行拆分,在start~end范围之间进行拆分 public void divide(int[] array,int[] tempArray,int start,int end){ int middle=(start+end)/2; //左数组范围是start~middle;右数组范围是middle+1~end //拆分递归方法的终止条件 if(start>=end) return; //如果没有终止就递归调用继续拆分 this.divide(array,tempArray,start,middle); this.divide(array,tempArray,middle+1,end); this.merge(array,tempArray,start,end); } /*这个方法用来对两个已经排序的子数组进行合并,将其重新排序并且记录合并时产生的逆序对数目,将在start和end范围之内的数组进行合并, 显然这个两个数组的分界点是(start+end)/2*/ public void merge(int[] array,int[] tempArray,int start,int end){ int middle=(start+end)/2; //左侧子数组是从start~middle;右侧子数组是从middle+1~end //现将其合并排序,统计逆序对数目 int leftPoint=start; int rightPoint=middle+1; //理解:每次调用merge()方法只是对start到end范围内的数据进行排序,因此用tempPoint指针来记录临时数组中填充进的数字的位置 int tempPoint=start; //对两个子数组进行遍历,直到一个数组遍历结束,防止数组访问越界 while(leftPoint<=middle&&rightPoint<=end){ //不构成逆序对,count不变,将较小的数值放入到temp数组中 if(array[leftPoint]
对一些小地方进行合并简化之后的代码:public class Solution { private long count; public int InversePairs(int [] array) { if(array==null||array.length==0) return 0; int[] temp=new int[array.length]; divid(array,temp,0,array.length-1); return (int)(count%1000000007); } public void divid(int[]array,int []temp,int low,int high){ if(low>=high) return; int mid=(low+high)/2; divid(array,temp,low,mid); divid(array,temp,mid+1,high); merge(array,temp,low,high); } public void merge(int[]array,int[]temp,int low,int high){ int lowend=(low+high)/2; int highpos=lowend+1; int temppos=low; int len=high-low+1; while(low<=lowend&&highpos<=high){ if(array[low]<=array[highpos]){ temp[temppos++]=array[low++]; //简化写法,节省代码 }else{ count+=(lowend-low+1)%1000000007; //改为count=count%1000000007+((middle-leftPoint+1)%1000000007);才通过 temp[temppos++]=array[highpos++]; //简化写法,节省代码 } } while(low<=lowend){ temp[temppos++]=array[low++]; } while(highpos<=high){ temp[temppos++]=array[highpos++]; } for(int i=len;i>0;i--,high--){ //for循环中一个分号可以写多个条件 array[high]=temp[high]; } }}