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