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

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

引用

CSDN

1.

https://blog.csdn.net/m0_74091276/article/details/145993192

本文详细介绍了如何计算数组中的逆序对数量，包括问题描述、解题思路、代码实现及解析。文章结构清晰，内容完整，涵盖了暴力解法和归并排序法两种解决方案，并附有详细的代码示例和解释。对于编程学习者来说，这篇文章具有较高的参考价值。

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