数组中的逆序对（C++）

目录

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)，适用于大规模数据。具体实现中，递归地拆分数组，合并时通过比较左右子数组元素，累加逆序对数量。归并排序法高效、稳定，且满足题目对时间和空间的复杂度要求，是解决该问题的推荐方案。