目录

1 问题描述

1.1 输入描述：

1.2 示例1

1.3 示例2

2 解题思路

2.1 暴力解法

2.2 归并排序法

3 代码实现

3.1 暴力解法

3.2 归并排序法

4 代码解析

4.1 暴力解法

4.1.1 初始化

4.1.2 判断是否是逆序对

4.2 归并排序法

4.2.1 InversePairs 主函数

4.2.2 归并排序 merge_sort__ 递归拆分

4.2.3 归并 merge__ 统计逆序对

5 总结

---

1 问题描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围：  对于 50%50% 的数据, size≤104size≤104
对于 100%100% 的数据, size≤105size≤105

数组中所有数字的值满足 0≤val≤1090≤val≤109

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)

1.1 输入描述：

题目保证输入的数组中没有的相同的数字

1.2 示例1

输入：

[1,2,3,4,5,6,7,0]

返回值：

7

1.3 示例2

输入：

[1,2,3]

返回值：

0

2 解题思路

2.1 暴力解法

通过两层嵌套循环，外层循环 i 遍历数组中的每个元素，内层循环 j 从 i+1 开始，检查 nums[i] > nums[j] 是否成立，若成立则递增逆序对计数 p++。最终，返回 p % 1000000007 以避免结果溢出。

2.2 归并排序法

采用归并排序的方法高效计算数组中的逆序对。在 InversePairs 函数中，调用 merge_sort__ 递归地对数组进行归并排序，并在合并过程中计算逆序对。merge_sort__ 先递归地将数组拆分为左右两部分，再在 merge__ 过程中合并，同时统计逆序对。合并时，如果左半部分的 arr[i] > arr[j]（j 来自右半部分），则意味着 arr[i] 及其后续所有元素均大于 arr[j]，因此逆序对数 ret 需要累加 (mid - i + 1)，并取模 1000000007 以防溢出。

3 代码实现

3.1 暴力解法

    int InversePairs(vector<int>& nums) {
        // write code here
        long long p = 0;
        int n = nums.size();
        for(int i = 0; i+1 < n; i++)
        {
            for(int j = i+1; j < n; j++)
            {
                if(nums[i] > nums[j])
                {
                    p++;
                }
            }
        }
        return fmod(p, 1000000007);
    }

3.2 归并排序法

class Solution {
private:
    const int kmod = 1000000007;
public:
    int InversePairs(vector<int> data) {
        int ret = 0;
        merge_sort__(data, 0, data.size() - 1, ret);
        return ret;
    }


    void merge_sort__(vector<int> &arr, int l, int r, int &ret) {
        if (l >= r) {
            return;
        }

        int mid = l + ((r - l) >> 1);
        merge_sort__(arr, l, mid, ret);
        merge_sort__(arr, mid + 1, r, ret);
        merge__(arr, l, mid, r, ret);
    }

    void merge__(vector<int> &arr, int l, int mid, int r, int &ret) {
        vector<int> tmp(r - l + 1);
        int i = l, j = mid + 1, k = 0;

        while (i <= mid && j <= r) {
            if (arr[i] > arr[j]) {
                tmp[k++] = arr[j++];
                // 奥妙之处
                ret += (mid - i + 1);
                ret %= kmod;
            }
            else {
                tmp[k++] = arr[i++];
            }
        }

        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= r) {
            tmp[k++] = arr[j++];
        }

        for (k = 0, i = l; i <= r; ++i, ++k) {
            arr[i] = tmp[k];
        }
    }
};

4 代码解析

4.1 暴力解法

4.1.1 初始化

        long long p = 0;
        int n = nums.size();

初始化，p用来计算逆序对个数，n为循环边界。 

4.1.2 判断是否是逆序对

        for(int i = 0; i+1 < n; i++)
        {
            for(int j = i+1; j < n; j++)
            {
                if(nums[i] > nums[j])
                {
                    p++;
                }
            }
        }

使用两层嵌套循环统计逆序对，外层循环 i遍历数组的前 n-1 个元素。内层循环 j从 i+1 开始，遍历 i 之后的元素，检查 nums[i] > nums[j] 是否成立。如果满足 nums[i] > nums[j]，则 p++ 记录一个逆序对。

4.2 归并排序法

4.2.1 InversePairs 主函数

int InversePairs(vector<int> data) {
    int ret = 0;
    merge_sort__(data, 0, data.size() - 1, ret);
    return ret;
}

ret 变量用于存储逆序对的个数。调用 merge_sort__ 对 data 进行归并排序，同时统计逆序对。

4.2.2 归并排序 merge_sort__ 递归拆分

void merge_sort__(vector<int> &arr, int l, int r, int &ret) {
    if (l >= r) {
        return;
    }

    int mid = l + ((r - l) >> 1);
    merge_sort__(arr, l, mid, ret);
    merge_sort__(arr, mid + 1, r, ret);
    merge__(arr, l, mid, r, ret);
}

该函数不断递归拆分数组，直到 l >= r（即子数组长度为 1）。递归调用 merge_sort__ 对左右子数组分别排序。最后调用 merge__ 进行合并并计算逆序对。 

4.2.3 归并 merge__ 统计逆序对

void merge__(vector<int> &arr, int l, int mid, int r, int &ret) {
    vector<int> tmp(r - l + 1);
    int i = l, j = mid + 1, k = 0;

    while (i <= mid && j <= r) {
        if (arr[i] > arr[j]) {
            tmp[k++] = arr[j++];
            // 统计逆序对数量
            ret += (mid - i + 1);
            ret %= kmod;
        } else {
            tmp[k++] = arr[i++];
        }
    }

    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r) tmp[k++] = arr[j++];

    for (k = 0, i = l; i <= r; ++i, ++k) {
        arr[i] = tmp[k];
    }
}

该方法利用双指针合并两个有序子数组，并在合并过程中统计逆序对。指针 i 遍历左半部分（l 到 mid），j 遍历右半部分（mid + 1 到 r）。当 arr[i] > arr[j] 时，说明 arr[i] 及其后续所有元素（mid - i + 1 个）都大于 arr[j]，构成逆序对，累加 ret 并对 1000000007 取模防止溢出。排序时，较小的元素先存入 tmp，保持整体有序，最终将 tmp 复制回 arr，完成归并排序。

5 总结

本文介绍了两种计算数组逆序对的方法：暴力解法和归并排序法。暴力解法使用两层嵌套循环，逐一比较元素，时间复杂度为O(n^2)，适用于小规模数据。归并排序法利用归并排序的分治思想，结合双指针合并两个有序子数组，并在合并过程中统计逆序对，时间复杂度降为O(n log n)，适用于大规模数据。具体实现中，递归地拆分数组，合并时通过比较左右子数组元素，累加逆序对数量。归并排序法高效、稳定，且满足题目对时间和空间的复杂度要求，是解决该问题的推荐方案。