题解 | 数组中的逆序对

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    //定义模数
    private static final int MOD = 1000000007;

    public int InversePairs (int[] nums) {
        //分治思想
        int len = nums.length;

        if (len < 2) {
            return 0;
        }

        //设置一个辅助数组，用于存储归并后已排好序的元素
        int[] temp = new int[len];

        int result = mergeSort(nums, 0, len - 1, temp) % MOD;

        return result;
    }

    //编写函数mergeSort用于递归计算逆序对个数
    private int mergeSort(int[] nums, int left, int right, int[] temp) {
        //判断是否子数组中仅包含一个元素，如果是则返回0个逆序对
        if (left >= right) {
            return 0;
        }

        //计算数组中元素的中位索引，并以此划分子数组
        int mid = left + (right - left) / 2;
        //定义cnt，记录子数组中逆序对的个数
        int cnt = 0;

        //1. 对左子数组进行划分递归，并且记录左子数组中的逆序对
        cnt = (cnt + mergeSort(nums, left, mid, temp)) % MOD;
        //2. 对右子数组进行划分递归，并且记录右子数组中的逆序对
        cnt = (cnt + mergeSort(nums, mid + 1, right, temp))%MOD;
        //3. 对左右子数组进行合并，并记录合并后的逆序对
        cnt = (cnt + merge(nums, temp, left, mid, right))%MOD;

        return cnt;
    }


    //编写函数合并子数组，并计算跨子数组的逆序对个数
    private int merge(int[] nums, int[]temp, int left, int mid, int right) {
        //设置指针i指向左子数组，指针j指向右子数组，k指向辅助数组temp，用于合并排序元素
        int i = left;
        int j = mid + 1;
        int k = left;

        //设置cnt记录逆序对的个数
        int cnt = 0;

        //1. 如果左子数组中的元素大于右子数组中元素，那么将右子数组归并于辅助数组中。
        //并且左子数组中元素，及其之后的元素都可记为逆序对
        //当左子数组中元素没有遍历完，且右子数组没遍历完时：
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k] = nums[i];
                k++;
                i++;
            } else {
                temp[k] = nums[j];
                k++;
                j++;
                cnt = (cnt + mid - i + 1) %MOD;
            }
        }

        //如果左半子数组还有剩余元素，将所有元素复制到辅助数组中
        while(i <= mid){
            temp[k] = nums[i];
            k++;
            i++;
        }

        //如果右半子数组还有剩余元素，将所有元素复制回辅助数组
        while(j <= right){
            temp[k] = nums[j];
            k++;
            j++;
        }

        //将辅助数组中的内容复制回原数组
        for(i = left; i<=right;i++){
            nums[i] = temp[i];
        }

        return cnt;
    }


}

这个题折磨了我有四五个小时。需要注意的有以下几点：

1. 归并排序的思想是如何应用到解题中的

我可以理解将整个数组不断划分为子数组，当子数组中元素为1时，返回逆序对cnt = 0；

但是在这个解题思路中从始至终数组本身并没有改变，变的只是left，mid，right索引值。

第一步是先关注左子数组，不断对左子数组进行划分并合并计算逆序对。左子数组的子数组合并完之后再处理右子数组。

右子数组再进行不断划分合并计算逆序对。直到只剩下一个左子数组和一个右子数组。最终再将左右合并。

这个过程可以在merge函数中不断打印当前传递数组与索引值进行查验和理解。

2. MOD细节

第一遍做题时，我只在最后输出结果时进行了磨数操作 % MOD。测试用例时都正常，唯独提交时，有一个测试用例无法通过。检查了很多遍觉得没有错误，百思不得其解。后询问deepseek，了解到如果测试用例中得出的逆序对非常大时，可能会出现整数溢出现象。例如，数组完全逆序时，逆序对的数量是 n(n-1)/2，其中 n 是数组长度。所以每一步更新cnt计数时，都采取磨数操作，确保返回值不超过数据类型的边界，导致结果错误。