#yyds干货盘点# 面试必刷TOP101：数组中的逆序对

1.简述：

描述

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

数据范围：  对于  的数据, 对于  的数据, 

数组中所有数字的值满足 

要求：空间复杂度 ，时间复杂度 

输入描述：

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

示例1

输入：

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

返回值：

7

示例2

输入：

[1,2,3]

返回值：

0

2.代码实现：

public class Solution {
int count = 0;
public int InversePairs(int [] array) {
// 长度小于2则无逆序对
if(array.length < 2)
return 0;
// 进入归并
mergeSort(array,0,array.length-1);
return count;
}

public void mergeSort(int[] array,int left,int right){
// 找分割点
int mid = left+(right-left)/2;
if(left < right){
// 左子数组
mergeSort(array,left,mid);
// 右子数组
mergeSort(array,mid+1,right);
// 并
merge(array,left,mid,right);
}
}

public void merge(int[] array,int left,int mid,int right){
// 创建临时数组，长度为此时两个子数组加起来的长度
int[] arr = new int[right-left+1];
// 临时数组的下标起点
int c = 0;
// 保存在原数组的起点下标值
int s = left;
// 左子数组的起始指针
int l = left;
// 右子数组的起始指针
int r = mid+1;
while(l <= mid && r <= right ){
// 当左子数组的当前元素小的时候，跳过，无逆序对
if(array[l] <= array[r]){
// 放入临时数组
arr[c] = array[l];
// 临时数组下标+1
c++;
// 左子数组指针右移
l++;
}else{ // 否则，此时存在逆序对
// 放入临时数组
arr[c] = array[r];
// 逆序对的个数为 左子数组的终点- 当前左子数组的当前指针
count += mid+1-l;
count %= 1000000007;
// 临时数组+1
c++;
// 右子数组的指针右移
r++;
}
}

// 左子数组还有元素时，全部放入临时数组
while(l <= mid)
arr[c++] = array[l++];
// 右子数组还有元素时，全部放入临时数组
while(r <= right)
arr[c++] = array[r++];
// 将临时数组中的元素放入到原数组的指定位置
for(int num:arr){
array[s++] = num;
}
}
}