剑指offer - 数组中的逆序对(Java实现)

题目链接：https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&&tqId=11188&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

• 归并排序
  归并排序算法采用经典的分治策略。
  分：将一个大问题分解成很多个小问题，这一步可以使用递归来解决；
  治：将"分"出来的小问题得到的答案"结合"在一起。
  这就是分而治之。

  思路，归并排序的分治过程如图：

  首先我们先来看排序过程需要多少次：2 + 1 = 3次，也就是 n / 2 + n / 4 .... n / (2 * k) -> n，所以归并排序的时间复杂度我们可以看成是 的。然后我们通过一个图看在合并的时候的详细过程：

  根据上图我们就可以知道我们什么时候可以记录逆序对的个数。下面给出AC代码：这里要说明的是如果在记录最终结果的时候我们使用一个静态的全局变量会导致有一组数据过不去（目前原因还不知道），我们要使用Java中的特性，即封装性来编写代码，不知道为什么一定要这样才能通过后台的测试样例？？？？

import java.util.*;

public class Solution {
    private int times;
    final int mod = 1000000007;
    public int InversePairs(int [] array) {
        if(array == null || array.length == 0) return 0;
        int[] temp = new int[array.length];
        mergeSort(array, 0, array.length - 1, temp);
        return times;
    }
    public void mergeSort(int[] array, int left, int right, int[] temp) {
        if(left < right) {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid, temp); //分
            mergeSort(array, mid + 1, right, temp);//分
            merge(array, left, mid, right, temp);//治
        }
    }
    public void merge(int[] array, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, cnt = 0;
        while(i <= mid && j <= right) {
            if(array[i] <= array[j]) {
                temp[cnt ++] = array[i ++];
            } else {//右边数组比较小,要越过左边的数字填充到左边
                temp[cnt ++] = array[j ++];
                times = (times + mid - i + 1) % mod;
            }
        }
        while(i <= mid) {//左边剩余的数字
            temp[cnt ++] = array[i ++];
        }
        while(j <= right) {//右边剩余的数字
            temp[cnt ++] = array[j ++];
        }
        for(int k = 0; k < cnt; ++ k) {//填充到原数组中
            array[left + k] = temp[k];
        }
    }
}