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

思路:

1. 归并排序是一种分治算法，它将一个数组分成两半，分别排序，然后将两个有序的子数组合并成一个有序的数组。这个算法的时间复杂度是O(nlogn)，满足题目的要求。
2. 定义一个mergeSort函数，它接收一个数组arr作为输入。在这个函数中，首先检查数组的长度，如果长度小于等于1，那么它不包含逆序对，直接返回0。
3. 接下来，找到数组的中点，并将数组分成两个子数组：left和right。然后，递归调用mergeSort函数来分别对左右两个子数组进行排序。
4. 在递归调用返回后，得到了两个已排序的子数组left和right。接下来，将它们合并成一个有序的数组，并在合并的过程中统计逆序对的数量。
5. 使用两个指针i和j分别指向左子数组和右子数组的起始位置，然后比较left[i]和right[j]的值。如果left[i]小于等于right[j]，那么它们是有序的，不会产生逆序对，将left[i]加入合并后的数组，并将i加1。
6. 如果left[i]大于right[j]，则说明left[i]及其后面的元素都大于right[j]，因此会产生逆序对。这时，将right[j]加入合并后的数组，并将j加1，同时将逆序对的数量增加left.length - i，因为在left中，left[i]到left[length - 1]都大于right[j]。
7. 重复步骤5和步骤6，直到其中一个子数组的元素全部被合并，此时我们将另一个子数组的剩余元素添加到合并后的数组中。
8. 最后，将合并后的有序数组复制回原始数组arr，并返回逆序对的数量。
9. 在inversePairs函数中，我们调用mergeSort来解决问题，并将结果对1000000007取模，最后输出逆序对的数量。

这段代码的关键点是使用归并排序的思想，在合并过程中统计逆序对的数量，同时对结果进行取模以防止溢出。这样，可以在O(nlogn)的时间复杂度内解决这个问题，同时满足题目要求的空间复杂度和时间复杂度。

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
function mergeSort(arr) {
  const mod = 1000000007;
  if (arr.length <= 1) {
    return 0; // 如果数组长度小于等于1，无逆序对
  }

  let count = 0; // 逆序对的数量
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);  // 左半部分
  const right = arr.slice(mid); // 右半部分

  count = (count + mergeSort(left)) % mod; // 递归处理左半部分
  count = (count + mergeSort(right)) % mod; // 递归处理右半部分
  
  let i = 0; // 左半部分的索引
  let j = 0; // 右半部分的索引
  const merged = [];

  while (i < left.length || j < right.length) {
    if (i >= left.length) { // 左半部分已经合并完成
      merged.push(right[j]); // 直接将右半部分合并到数组中
      j++;
    } else if (j >= right.length) { // 右半部分已经合并完成
      merged.push(left[i]); // 直接将左半部分合并到数组种
      i++;
    } else if (left[i] <= right[j]) { // 如果left[i]小于等于right[j]，那么它们是有序的
      merged.push(left[i]); // 将left[i]加入合并后的数组
      i++; // 并将i加1。
    } else {
      count = (count + left.length - i) % mod; // 如果left[i]大于right[j]，则说明left[i]及其后面的元素都大于right[j]
      merged.push(right[j]); // 将right[j]加入合并后的数组
      j++; // 并将j加1
    }
  }
  // 将合并后的有序数组 merged 中的元素复制回原始数组 arr。
  for (let k = 0; k < merged.length; k++) {
    arr[k] = merged[k];
  }
  
  return count;
}

function InversePairs(nums) {
  return mergeSort(nums);
}
module.exports = {
  InversePairs: InversePairs,
};