数组中的逆序对
题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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(n)个数进行比较。时间复杂度为o(n^2)
思路二
解法一:
public class Test18 {
public int InversePairs(int [] array) {
if(array==null || array.length<=0){
return 0;
}
int pairsNum=mergeSort(array,0,array.length-1);
return pairsNum;
}
public int mergeSort(int[] array,int left,int right){
if(left==right){
return 0;
}
int mid=(left+right)/2;
int leftNum=mergeSort(array,left,mid);
int rightNum=mergeSort(array,mid+1,right);
return (Sort(array,left,mid,right)+leftNum+rightNum)%1000000007;
}
public int Sort(int[] array,int left,int middle,int right){
int current1=middle;
int current2=right;
int current3=right-left;
int temp[]=new int[right-left+1];
int pairsnum=0;
while(current1>=left && current2>=middle+1){
if(array[current1]>array[current2]){
temp[current3--]=array[current1--];
pairsnum+=(current2-middle); //这个地方是current2-middle!!!!
if(pairsnum>1000000007)//数值过大求余
{
pairsnum%=1000000007;
}
}else{
temp[current3--]=array[current2--];
}
}
while(current1>=left){
temp[current3--]=array[current1--];
}
while(current2>=middle+1){
temp[current3--]=array[current2--];
}
//将临时数组赋值给原数组
int i=0;
while(left<=right){
array[left++]=temp[i++];
}
return pairsnum;
}
public static void main(String[] args){
Test18 test18 = new Test18();
int[] arr = {1,2,3,4,5,6,7,0};
int count = test18.InversePairs(arr);
System.out.println(count);
}
}
解法二:参考归并排序
public class nixudui {
public int InversePairs(int [] array) {
if(array==null || array.length<=0){
return 0;
}
int pairsNum=merSort(array,0,array.length-1);
return pairsNum;
}
public int merSort(int[] arr,int left,int right){
int lCount = 0;
int rCount = 0;
int pairCount = 0;
if(left<right){
int mid = (left+right)/2;
lCount = merSort(arr,left,mid);//左边归并排序,使得左子序列有序
rCount = merSort(arr,mid+1,right);//右边归并排序,使得右子序列有序
pairCount = merge(arr,left,mid,right);//合并两个子序列
}
return (lCount + rCount + pairCount)%1000000007;
}
private int merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];//ps:也可以从开始就申请一个与原数组大小相同的数组,因为重复new数组会频繁申请内存
int count = 0;
//左边数组的长度
int n1 = mid - left + 1;
//右边数组的长度
int n2 = right - mid;
int[] LArr = new int[n1];
int[] RArr = new int[n2];
for(int i = 0;i < n1;i++){
int j = 0;
LArr[i] = arr[j++];
}
for(int i = 0;i < n2;i++){
int j = mid + 1;
RArr[i++] = arr[j++];
}
int i = n1 - 1;
int j = n2 - 1;
for(int k = right; k >= left; k--){
if(LArr[i] > RArr[j]){
count += (j + 1);
temp[k] = LArr[i];
i -= 1;
}else {
temp[k] = RArr[j];
j -= 1;
}
}
//将temp中的元素全部拷贝到原数组中
int s=0;
while(left<=right){
arr[left++]=temp[s++];
}
return count;
}
public static void main(String args[]){
Test18 test18 = new Test18();
int[] test = {637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575};
int count = test18.InversePairs(test);
System.out.println(count);
}
}
参考:
《剑指offer》