#yyds干货盘点# 解决剑指offer（数组中的逆序对） _剑指OFFER

业无高卑志当坚，男儿有求安得闲？这篇文章主要讲述#yyds干货盘点# 解决剑指offer：数组中的逆序对相关的知识，希望能为你提供帮助。
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
public int mod = 1000000007;
public int mergeSort(int left, int right, int [] data, int [] temp)
//停止划分
if(left > = right)
return 0;
//取中间
int mid = (left + right) / 2;
//左右划分合并
int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp);
//防止溢出
res %= mod;
int i = left, j = mid + 1;
for(int k = left; k < = right; k++)
temp[k] = data[k];
for(int k = left; k < = right; k++)
if(i == mid + 1)
data[k] = temp[j++];
else if(j == right + 1 || temp[i] < = temp[j])
data[k] = temp[i++];
//左边比右边大，答案增加
else
data[k] = temp[j++];
// 统计逆序对
res += mid - i + 1;

return res % mod;

public int InversePairs(int [] array)
int n = array.length;
int[] res = new int[n];
return mergeSort(0, n - 1, array, res);