题解 | #数组中的逆序对#

import java.util.ArrayList;

public class Solution {
    
    public static Long P = 0L;
    
    public int InversePairs(int [] array) {
        if (0 == array.length) {
            return 0;
        }
        if (1 == array.length) {
            return 1;
        }
        // 定义一个整型变量 P，用于存储最终的返回结果
        int[] rs = MergeSort(array);
        return (int) (P % 1000000007);
    }
    
    // 归并排序的实现
    public static int[] MergeSort(int[] array) {
        // 省略特殊情况的判断啦！因为在调用该函数前我们已经对某些特殊的 array 进行了过滤，所以这里就不再进行类似的操作啦！
        if (1 == array.length) {
            return array;
        }
        // 进行递归调用
        int[] leftMerge = MergeSort(Arrays.copyOfRange(array, 0, array.length / 2));
        int[] rightMerge = MergeSort(Arrays.copyOfRange(array, array.length / 2, array.length));
        // 进行归并操作
        // 定义一个指针，用于指向 leftMerge
        int leftP = 0;
        // 定义一个指针，用于指向 rightMerge
        int rightP = 0;
        // 定义一个队列，用于存放临时数据
        ArrayList<Integer> al = new ArrayList<>();
        while (leftP < leftMerge.length && rightP < rightMerge.length) {
            if (leftMerge[leftP] > rightMerge[rightP]) {
                // 注意：这里不是单纯的 P++
                P += (rightMerge.length - rightP);
                al.add(leftMerge[leftP]);
                leftP++;
            }
            else if (leftMerge[leftP] < rightMerge[rightP]) {
                al.add(rightMerge[rightP]);
                rightP++;
            }
        }
        if (leftP == leftMerge.length) {
            while (rightP < rightMerge.length) {
                al.add(rightMerge[rightP]);
                rightP++;
            }
        }
        else if (rightP == rightMerge.length) {
            while (leftP < leftMerge.length) {
                al.add(leftMerge[leftP]);
                leftP++;
            }
        }
        return al.stream().mapToInt(Integer::intValue).toArray();
    }
}