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

import java.util.Arrays;
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();
    }
    */

    /**********************************************************************************/
    public long ans = 0l;

    public int InversePairs(int[] array) {
        mergeSort(array);
        return (int) (ans % 1000000007);
    }

    public void mergeSort(int[] nums) {
        if (0 == nums.length || 1 == nums.length) {
            return;
        }
        process(nums, 0, nums.length - 1);
    }

    public void process(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + ((end - start) >> 1);
        process(nums, start, mid);
        process(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }

    public void merge(int[] nums, int start, int mid, int end) {
        int[] help = new int[end - start + 1];
        int index = 0;
        int p1 = start;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= end) {
            ans += nums[p1] > nums[p2] ? (end - p2 + 1) : 0;
            help[index++] = nums[p1] > nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= mid) {
            help[index++] = nums[p1++];
        }
        while (p2 <= end) {
            help[index++] = nums[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            nums[start + i] = help[i];
        }
    }
}