public class Solution { // 模数，用于防止溢出 public int mod = 1000000007; /** * 归并排序的变种，既排序数组也计算逆序对 * @param left 区间左端点 * @param right 区间右端点 * @param data 原数组 * @param temp 临时数组 * @return 逆序对数量 */ public int mergeSort(int left, int right, int [] data, int [] temp) { // 如果左端点大于或等于右端点，说明只有一个元素或没有元素，直接返回0 if (left >= right) return 0; // 计算区间中间位置 int mid = (left + right) / 2; // 递归地对左半部分和右半部分分别进行排序，并加上各自的逆序对数量 int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); // 防止res超出int的范围 res %= mod; // 初始化左右部分的起始指针 int i = left, j = mid + 1; // 将当前区间的数据复制到临时数组 for(int k = left; k <= right; k++) temp[k] = data[k]; // 对当前区间进行归并操作 for(int k = left; k <= right; k++) { // 如果左半部分已经完全归并，直接归并右半部分 if (i == mid + 1) data[k] = temp[j++]; // 如果右半部分已经完全归并，或者左半部分当前值小于等于右半部分当前值，归并左半部分 else if (j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++]; // 否则，存在逆序对，归并右半部分，并统计逆序对数量 else { data[k] = temp[j++]; // 添加逆序对数量 res += mid - i + 1; } } // 返回当前区间的逆序对数量 return res % mod; } /** * 计算数组中的逆序对数量 * @param array 输入数组 * @return 逆序对数量 */ public int InversePairs(int [] array) { int n = array.length; int[] res = new int[n]; // 创建临时数组 // 对整个数组进行归并排序并计算逆序对数量 return mergeSort(0, n - 1, array, res); } }