计数逆序对（Count Inversions） 题目描述 给定一个整数数组，计算数组中的逆序对数量。逆序对的定义是：对于数组中的两个元素 (i, j) ，如果 i < j 且 nums[i] > nums[j] ，则 (i, j) 构成一个逆序对。例如，数组 [2, 4, 1, 3, 5] 的逆序对包括 (2,1) 、 (4,1) 、 (4,3) ，因此逆序对数量为 3。 解题思路 直接暴力解法需要遍历所有元素对，时间复杂度为 O(n²)。更高效的方法是 利用归并排序的过程 ，在合并两个有序子数组时统计逆序对。具体步骤如下： 分治策略 ： 将数组从中间分为左右两个子数组。 递归计算左子数组的逆序对数量、右子数组的逆序对数量。 计算跨越左右子数组的逆序对数量（即左子数组中元素大于右子数组中元素的情况）。 合并时的统计 ： 在合并左右两个有序子数组时，若左子数组当前元素 left[i] 大于右子数组当前元素 right[j] ，则左子数组中从 i 到末尾的所有元素都会与 right[j] 构成逆序对（因为左右子数组已分别有序）。 详细步骤 递归分割 ： 若数组长度 ≤1，逆序对数量为 0。 否则，计算中点 mid ，递归处理左半部分 [left, mid] 和右半部分 [mid+1, right] 。 合并与统计 ： 设置指针 i 遍历左子数组， j 遍历右子数组。 比较 left[i] 和 right[j] ： 若 left[i] ≤ right[j] ，将 left[i] 放入合并数组， i++ 。 若 left[i] > right[j] ，说明 left[i] 及其后所有元素均大于 right[j] ，此时逆序对增加 mid - i + 1 （左子数组剩余元素个数），将 right[j] 放入合并数组， j++ 。 合并剩余元素 ： 将左或右子数组剩余元素依次放入合并数组。 示例演示 以数组 [2, 4, 1, 3, 5] 为例： 分割为 [2,4,1] 和 [3,5] ，分别递归计算逆序对。 左子数组 [2,4,1] 分割为 [2,4] 和 [1] ： 合并 [2,4] 和 [1] ：比较 2>1，逆序对 +2（因左子数组剩余 2 个元素），合并后为 [1,2,4] 。 右子数组 [3,5] 无逆序对。 合并 [1,2,4] 和 [3,5] ： 1 <3，放入 1； 2 <3，放入 2； 4>3，逆序对 +1（左子数组剩余 1 个元素），放入 3； 4 <5，放入 4； 放入剩余 5。 总逆序对 = 2（左子数组）+ 0（右子数组）+ 1（跨越合并）= 3。 关键点 利用归并排序的 稳定性 确保统计不重不漏。 时间复杂度为 O(n log n)，空间复杂度 O(n)。