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

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        return mergeSort(nums, 0, nums.length - 1) % 1000000007;
    }

    /**
     * 归并排序，统计逆序对的数量
     * @param nums 数组
     * @param left 左边界
     * @param right 右边界
     * @return 逆序对的数量
     */
    public int mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (left + right) / 2;
        // 分别对左右两个部分进行归并排序
        int leftNum = mergeSort(nums, left, mid);
        int rightNum = mergeSort(nums, mid + 1, right);
        // 合并左右两个有序数组并统计逆序对数量
        int leftAndRight = merge(nums, left, mid, right);
        // 返回当前合并阶段发现的逆序对数量
        return rightNum + leftNum + leftAndRight;
    }

    /**
     * 合并两个有序数组，并统计逆序对的数量
     * @param nums 数组
     * @param left 左边界
     * @param mid 中间索引
     * @param right 右边界
     * @return 当前合并阶段发现的逆序对数量
     */
    public int merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int leftStart = left;
        int rightStart = mid + 1;
        int index = 0;
        int count = 0; // 统计逆序对的数量

        while (leftStart <= mid && rightStart <= right) {
            if (nums[leftStart] <= nums[rightStart]) {
                temp[index++] = nums[leftStart++];
            } else {
                temp[index++] = nums[rightStart++];
                // 统计逆序对的数量，因为右边数组有一个元素小于左边数组的当前元素，说明构成了逆序对
                count += mid - leftStart + 1;
                // 对逆序对数量进行取模，避免溢出
                count %= 1000000007;
            }
        }

        // 将左边数组剩余的元素复制到临时数组
        while (leftStart <= mid) {
            temp[index++] = nums[leftStart++];
        }

        // 将右边数组剩余的元素复制到临时数组
        while (rightStart <= right) {
            temp[index++] = nums[rightStart++];
        }

        // 将临时数组中的元素拷贝回原数组
        for (int i = 0; i < temp.length; i++) {
            nums[left + i] = temp[i];
        }

        // 返回当前合并阶段发现的逆序对数量
        return count;
    }
}