本题为剑指offer面试题36
测试地址：https://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5
[编程题]数组中的逆序对
热度指数：67584时间限制：1秒空间限制：32768K
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
输入例子:
1,2,3,4,5,6,7,0
输出例子:
7
package go.jacob.day510;
public class Demo3 {
// result用来存储交换次数，temp为归并排序所需的额外空间
private int result;
static int[] temp;
public int InversePairs(int[] array) {
// 考虑无效输入
if (array == null || array.length <= 0) {
return 0;
}
// 注意：因为result设置为成员变量，所以每一次调用该方法都要初始化为0！
result = 0;
temp = new int[array.length];
sort(array, 0, array.length - 1);
return result;
}
public void sort(int[] array, int left, int right) {
if (left == right) {
return;
}
int mid = (left + right) / 2;
sort(array, left, mid);
sort(array, mid + 1, right);
merge(array, left, mid, right);
}
public void merge(int[] array, int left, int middle, int right) {
int i = middle;
int j = right;
int index = right;
//把本次循环用到的数字拷贝进temp
for (int k = left; k <= right; k++) {
temp[k] = array[k];
}
while (i >= left && j >= middle + 1) {
if (temp[i] > temp[j]) {
array[index--] = temp[i--];
//逆序对数目为第二个子数组中剩余的数字
result += j - middle;
// 数值过大要进行求余
if (result > 1000000007)
{
result %= 1000000007;
}
} else
array[index--] = temp[j--];
}
while (i >= left)
array[index--] = temp[i--];
while (j >= middle + 1)
array[index--] = temp[j--];
}
}