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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        // write code here
        // 左程云老师讲过，通过归并排序过程中的左右两个字串的比较，可以实现逆序对的统计

        // 算法的时间复杂度O(NlogN)，空间复杂度O(N)

        // 调用归并排序的递归执行方法
        int count = process(nums, 0, (nums.length - 1));
        // 注意题目要求，对1000000007取模
        return count % 1000000007;
    }

    // 递归执行方法
    public int process(int[] nums, int l, int r) {
        // 递归出口
        if (l == r) {
            return 0;
        }
        // 计算中间索引
        int mid = (l + r) / 2;
        // 返回递归过程产生的逆序对数量
        int count = process(nums, l, mid) +
                    process(nums, mid + 1, r) +
                    compareAndMerge(nums, l, mid, r);
        // 注意题目要求，对1000000007取模
        return count % 1000000007;
    }

    // 比较与归并方法
    public int compareAndMerge(int[] nums, int l, int mid, int r) {
        // 记录逆序对的个数
        int count = 0;

        // 比较，归并
        int[] tempNums = new int[r - l + 1];
        // nums的左半区下标
        int leftIndex = l;
        // nums的右半区下标
        int rightIndex = mid + 1;
        // tempNums的下标
        int tempIndex = 0;
        while (leftIndex <= mid && rightIndex <= r) {
            // 请注意，归并排序merge的一个前提是，左右两个半区各自有序
            if (nums[leftIndex] < nums[rightIndex]) {
                // 左边 < 右边，则左边先进入tempNums中，leftIndex和tempIndex都++
                tempNums[tempIndex] = nums[leftIndex];
                leftIndex++;
            } else {
                // 左边 > 右边，则右边先进入tempNums中，rightIndex和tempIndex都++
                // 注意！此时算作逆序对！
                tempNums[tempIndex] = nums[rightIndex];
                rightIndex++;
                // tempNums[leftIndex]大，说明从leftIndex到mid上的数都更大，逆序数要全算上
                count += (mid - leftIndex + 1);
                // 注意题目要求，对1000000007取模
                count %= 1000000007;
            }
            tempIndex++;
        }
        // 此时退出了循环，要么leftIndex越界，要么rightIndex越界，以下两个while最多执行一个
        while (leftIndex <= mid) {
            // 右边的rightIndex先越界了，说明左边剩下的元素都比右边的大，把左边剩下的元素全部送进tempNums中
            // 注意！这里的逆序对已经被上一个while中考虑到了
            tempNums[tempIndex] = nums[leftIndex];
            leftIndex++;
            tempIndex++;
        }
        while (rightIndex <= r) {
            // 左边的leftIndex先越界了，说明右边剩下的元素都比左边的大，把右边剩下的元素全部送进tempNums中
            tempNums[tempIndex] = nums[rightIndex];
            rightIndex++;
            tempIndex++;
        }

        // 最后，把tempNums排好序的内容写回nums的对应位置
        for (int i = 0; i < tempNums.length; i++) {
            nums[l + i] = tempNums[i];
        }

        // 返回统计到的逆序数
        return count;
    }
}