每日一题-数组中的逆序对

问题描述

给定一个整数数组，要求计算数组中的逆序对数。逆序对的定义是：在数组中，如果某个元素比其后面的元素大，那么它们构成一个逆序对。我们需要返回逆序对的总数，并将结果对$10^9+7$取模。

例如，对于输入数组 [1, 2, 3, 4, 5, 6, 7, 0]，逆序对的数量为 7。

解题思路

本题可以利用归并排序的思想来解决。归并排序本身具有$O(n\log n)$的时间复杂度，而我们可以在归并的过程中统计逆序对。具体做法是，当我们将两个有序子数组合并时，遇到左边子数组的某个元素大于右边子数组的元素时，意味着左边的这个元素和右边当前的元素之间以及左边该元素之后的所有元素都构成逆序对。

视频讲解

建议先看下B站视频

代码实现

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007  // 结果对 1000000007 取模

// 全局变量
static unsigned int ret = 0;    // 用于存储逆序对的总数
int* sort_arr = NULL;  // 临时数组，用于合并时存储排序结果

// 合并排序并计算逆序对
void _merge_sort(int* arr, int *temp, int left, int mid, int right) {
    // 左边部分的起始和结束位置，右边部分的起始和结束位置
    int start1 = left, end1 = mid, start2 = mid + 1, end2 = right, i = left;

    // 合并两个子数组并计算逆序对
    while (start1 <= end1 && start2 <= end2) {
        if (arr[start1] <= arr[start2]) {
            // 如果左边的元素小于等于右边的元素，将左边的元素放入临时数组
            temp[i++] = arr[start1++];
        } else {
            // 如果左边的元素大于右边的元素，所有左边的元素都和当前右边元素形成逆序对
            ret += (mid - start1) + 1;
            ret %= MOD;  // 防止结果超出范围
            temp[i++] = arr[start2++];
        }
    }

    // 如果左边子数组还有剩余元素，直接复制到临时数组
    while (start1 <= end1) {
        temp[i++] = arr[start1++];
    }

    // 如果右边子数组还有剩余元素，直接复制到临时数组
    while (start2 <= end2) {
        temp[i++] = arr[start2++];
    }

    // 将临时数组的内容复制回原数组
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

// 递归分治计算逆序对
void _InversePairs(int *arr, int *temp, int left, int right) {
    // 如果区间大小为1或无元素，不需要再分割，直接返回
    if (left >= right) {
        return;
    }

    // 计算中间位置
    int mid = (left + right) >> 1;

    // 递归处理左半部分
    _InversePairs(arr, temp, left, mid);

    // 递归处理右半部分
    _InversePairs(arr, temp, mid + 1, right);

    // 合并左右两部分并统计逆序对
    _merge_sort(arr, temp, left, mid, right);
}

int InversePairs(int* data, int dataLen) {
    // 初始化逆序对计数器
    ret = 0;

    // 为临时数组分配内存
    sort_arr = malloc(sizeof(int) * dataLen);

    // 调用递归函数计算逆序对
    _InversePairs(data, sort_arr, 0, dataLen - 1);

    // 释放临时数组的内存
    if (sort_arr) {
        free(sort_arr);
        sort_arr = NULL;  // 防止野指针
    }

    // 返回逆序对的数量，取模 1000000007
    return ret % MOD;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 0};
    int len = sizeof(arr) / sizeof(arr[0]);

    // 调用函数计算逆序对
    int result = InversePairs(arr, len);

    // 输出结果
    printf("逆序对的数量: %d\n", result);
    return 0;
}

代码解释

1. _merge_sort 函数：这个函数是归并排序的核心部分。它不仅将两个子数组合并成一个有序数组，还在合并过程中计算逆序对的数量。每当遇到左边子数组的元素大于右边子数组的元素时，就意味着左边的所有元素都与当前右边元素形成逆序对。

2. _InversePairs 函数：这是一个递归函数，负责将数组分割为更小的部分，直到子数组只有一个元素。然后，通过调用 _merge_sort 合并并统计逆序对。

3. InversePairs 函数：这是用户调用的主要函数，它负责初始化数据并分配内存。最后，返回计算结果。

4. main 函数：用于测试代码，计算给定数组中的逆序对。

测试用例

• 示例1
  输入：[1, 2, 3, 4, 5, 6, 7, 0]
  输出：7
  解析：共有7个逆序对。

• 示例2
  输入：[1, 2, 3]
  输出：0
  解析：没有逆序对。

总结

使用归并排序来计算逆序对是一种高效的解决方法，尤其是在数据量较大时，能够将时间复杂度控制在$O(n\log n)$，比暴力法的$O(n^2)$要快得多。通过修改传统的归并排序，利用合并过程中对逆序对的计数，可以有效地解决此问题。

注意

int 和 unsigned int 在 C 语言中的使用

在大多数系统上，int 通常是 32 位，表示的范围是$-2^{31}$到$2^{31}-1$，即从 -2147483648 到 2147483647。
unsigned int 是无符号类型，没有负数，因此它的最大值更高。例如，在32位系统中，unsigned int 的范围是从 0 到 4294967295。

为什么选择 unsigned int？

题目要求对 1000000007 取模的结果输出。理论上，int 是足够的，但考虑到数组的长度最大为$10^5$，计算逆序对的数量可能会达到以下估算值：
$$\frac{10^5\times (10^5-1)}{2}\approx 5\times 10^9$$
这种情况下，int 的最大值 $2^{31}-1=2147483647$ 会无法满足需求，因此需要使用 unsigned int。尽管最大值 $4294967295$ 可能不够用，但对于大多数实际情况来说，它已经足够，经过我的计算，必须要保证十万个数组中，至少92,682个数是逆序，才能越界，根据正态分布，那么这种概率确实不大。

代码整体思路

这道题主要采用分治法（divide and conquer）来解决。首先将数组分成小的区间，计算每个小区间的逆序对，然后通过归并排序的方法，计算左右区间之间的逆序对。

步骤：

1. 分治：将数组分成两个子数组，递归地计算各个子数组的逆序对。
2. 归并排序：在归并两个有序子数组时，如果左边的元素小于右边的元素，那么它们是正常的排序。但如果左边的元素大于右边的元素，则构成逆序对。逆序对的数量等于mid - i + 1，其中i是左子数组的当前元素索引。
3. 递归合并：通过递归地分治并合并两个有序数组，同时计算逆序对。

总结：

• 采用了分治的思路，将问题拆解为小区间之间的逆序对计算。
• 通过归并排序合并两个区间时，顺便统计跨区间的逆序对。
• 对待这种题目，不必被复杂的计算方式吓倒，了解如何用递归和归并排序的方式计算逆序对是解题的关键。