35 数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例：

输入: [1, 2, 3, 4, 5, 6, 7, 0]
输出: 7 (1>0, 2>0, 3>0, 4>0, 5>0, 6>0, 7>0)

解题思路

核心思想：归并排序。在归并过程中统计逆序对。

关键步骤：

1. 归并排序时，当左边的元素大于右边的元素时，左边剩余的所有元素都与右边当前元素构成逆序对
2. 将逆序对的数量累加

时间复杂度：O(n log n) 空间复杂度：O(n)

Python 实现

def inverse_pairs(nums):
    """
    求数组中的逆序对数量

    Args:
        nums: 整数数组

    Returns:
        int: 逆序对的数量
    """
    if not nums:
        return 0

    count = 0
    temp = [0] * len(nums)

    def merge_sort(left, right):
        nonlocal count

        if left >= right:
            return

        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid + 1, right)

        # 归并并统计逆序对
        i, j, k = left, mid + 1, left

        while i <= mid and j <= right:
            if nums[i] <= nums[j]:
                temp[k] = nums[i]
                i += 1
            else:
                temp[k] = nums[j]
                count += mid - i + 1  # nums[i..mid] 都大于 nums[j]
                j += 1
            k += 1

        while i <= mid:
            temp[k] = nums[i]
            i += 1
            k += 1

        while j <= right:
            temp[k] = nums[j]
            j += 1
            k += 1

        for k in range(left, right + 1):
            nums[k] = temp[k]

    merge_sort(0, len(nums) - 1)
    return count


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [1, 2, 3, 4, 5, 6, 7, 0],
        [7, 5, 6, 4],
        [1, 2, 3],
        [3, 2, 1],
    ]

    for nums in test_cases:
        print(f"{nums} → 逆序对数量: {inverse_pairs(nums[:])}")

# 输出:
# [1, 2, 3, 4, 5, 6, 7, 0] → 逆序对数量: 7
# [7, 5, 6, 4] → 逆序对数量: 5
# [1, 2, 3] → 逆序对数量: 0
# [3, 2, 1] → 逆序对数量: 3

图解

归并排序统计逆序对过程示例: [7, 5, 6, 4]

归并过程:
[7] [5] [6] [4]
  ↓ 归并
[5,7] [4,6]  归并[7,5]时: 7>5，count+=1
  ↓ 归并
[4,5,6,7]

归并[5,7]和[4,6]:
- 5>4: count+=2 (5,7都>4)
- 5<=6: 取5
- 7>6: count+=1 (7>6)
- 取6,7

总逆序对: 1 + 2 + 1 = 4

验证:
(7,5), (7,6), (7,4), (5,4), (6,4) = 5对