逆序对

逆序对的定义与朴素解法是什么？

• 逆序对: 满足 i < j 且 nums[i] > nums[j] 的数对;
• 朴素解法: 双重循环枚举所有数对, 时间复杂度 O(n^2);
• 目标: 在 O(n log n) 内统计逆序对数量;

为什么归并排序可以统计逆序对？

• 合并阶段比较左段的 nums[i] 与右段的 nums[j];
• 当 nums[i] > nums[j] 时, 左段区间 [i, mid] 的所有元素都大于 nums[j];
• 因此一次比较可直接累加 mid - i + 1 个逆序对;
• 每个逆序对只在合并阶段被计数一次, 不重不漏;

逆序对如何实现？

function reversePairs(record: number[]): number {
  let res = 0;

  const merge = (nums: number[], left: number, mid: number, right: number): void => {
    const tmp = new Array(right - left + 1);
    let i = left;
    let j = mid + 1;
    let k = 0;
    while (i <= mid && j <= right) {
      if (nums[i] <= nums[j]) {
        tmp[k++] = nums[i++];
      } else {
        tmp[k++] = nums[j++];
        res += mid - i + 1;
      }
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= right) tmp[k++] = nums[j++];
    for (k = 0; k < tmp.length; k++) nums[left + k] = tmp[k];
  };

  const mergeSort = (nums: number[], left: number, right: number): void => {
    if (left >= right) return;
    const mid = Math.floor((left + right) / 2);
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
  };

  mergeSort(record, 0, record.length - 1);
  return res;
}

逆序对的复杂度是多少？

• 时间复杂度: O(n log n), 与归并排序相同;
• 空间复杂度: O(n), 合并需要临时数组;