题解 | 数组中的逆序对

import java.util.*;


public class Solution {
   // 定义模数，用于防止结果溢出
    private static final int mod = 1000000007;

    /**
     * 使用归并排序计算逆序对数量
     *
     * @param nums  待排序数组
     * @param left  左边界索引
     * @param right 右边界索引
     * @return 逆序对数量
     */
    private static long mergeSort(int[] nums, int left, int right) {
        // 递归终止条件：当区间只有一个元素或为空时，返回0
        if (left >= right) {
            return 0;
        }

        // 计算中间位置，使用位运算防止溢出
        int mid = left + ((right - left) >> 1);
        // 分治计算左右区间，并立即取模
        long res = (mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right)) % mod;

        // 创建临时数组用于合并
        int[] temp = new int[right - left + 1];
        int i = left;      // 左区间指针
        int j = mid + 1;   // 右区间指针
        int k = 0;         // 临时数组指针

        // 合并两个有序区间
        while (i <= mid && j <= right) {
            // 严格判断nums[i] <= nums[j]，仅大于时统计逆序对
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                // 累加后立即取模，防止溢出
                // 当nums[i] > nums[j]时，左区间从i到mid的所有元素都大于nums[j]
                res = (res + mid - i + 1) % mod;
            }
        }
        // 拷贝左区间剩余元素
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        // 拷贝右区间剩余元素
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        // 覆盖回原数组
        for (k = 0, i = left; k < temp.length; k++, i++) {
            nums[i] = temp[k];
        }
        return res;
    }

    /**
     * 计算数组中的逆序对数量
     *
     * @param nums 输入的整数数组
     * @return 逆序对的数量，结果对1000000007取模
     */
    public int InversePairs(int[] nums) {
        // 如果数组为null或长度小于等于1，则逆序对数量为0
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        // 调用归并排序算法计算逆序对数量，并对结果取模防止溢出
        return (int) (mergeSort(nums, 0, nums.length - 1) % mod);
    }

}