C++面试题（37）-----数组中的逆序对（求数组中逆序对的个数）

• 操作系统：ubuntu22.04
• IDE:Visual Studio Code
• 编程语言：C++11

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个“逆序对”。输入一个数组，求出这个数组中逆序对的总数。

示例：

输入: [7, 5, 6, 4]
输出: 5
解释: 有如下逆序对：
(7,5), (7,6), (7,4), (5,4), (6,4)

解法思路：归并排序思想 + 分治法

这是一个经典的分治算法问题，和「归并排序」非常类似。

我们使用归并排序的思想来统计逆序对数量，基本思路是：

• 将数组分成两半；
• 分别统计左右两半内部的逆序对数量；
• 然后合并两个有序子数组，并统计跨越左右的逆序对数量；
• 最终总逆序对 = 左边内部 + 右边内部 + 跨越中间部分。

我们来一步一步还原整个归并和统计逆序对的过程。
原始数组拆分后：

左边排序后：[5, 7]
右边排序后：[4, 6]

我们要将它们合并成一个有序数组，并在这个过程中统计跨越左右部分的逆序对数量。
合并时的指针设置：

i = left = 0   // 指向左边数组 [5, 7]
j = mid + 1 = 2 // 指向右边数组 [4, 6]
k = 0          // 指向临时数组 temp

第一步比较：5 vs 4

5 > 4 → 发现是一个逆序对；
因为左边数组从 i 到 mid（也就是 5 和 7）都大于 4；
所以这一轮贡献了 mid - i + 1 = 1 - 0 + 1 = 2 个逆序对；
把 4 放入 temp，j++。

第二步比较：5 vs 6

5 < 6 → 不构成逆序对；
把 5 放入 temp，i++；
没有贡献逆序对。

第三步比较：7 vs 6

7 > 6 → 构成逆序对；
左边从 i=1 到 mid=1（只有 7）都大于 6；
贡献了 mid - i + 1 = 1 - 1 + 1 = 1 个逆序对；
把 6 放入 temp，j++。

第四步：剩余元素复制

把 7 放入 temp；
没有新的逆序对产生。

✅ 总结一下贡献的逆序对：

代码

#include <vector>

using namespace std;

class Solution {
private:
    int mergeSortAndCount( vector< int >& nums, vector< int >& temp, int left, int right )
    {
        if ( left >= right )
            return 0;  // 没有逆序对

        int mid   = left + ( right - left ) / 2;
        int count = 0;

        // 分别统计左边和右边的逆序对
        count += mergeSortAndCount( nums, temp, left, mid );
        count += mergeSortAndCount( nums, temp, mid + 1, right );

        // 合并两个有序数组并统计交叉逆序对
        int i = left, j = mid + 1, k = left;

        while ( i <= mid && j <= right )
        {
            if ( nums[ i ] <= nums[ j ] )
            {
                temp[ k++ ] = nums[ i++ ];
            }
            else
            {
                // nums[i] > nums[j]，说明从 i 到 mid 的所有元素都与 nums[j] 构成逆序对
                temp[ k++ ] = nums[ j++ ];
                count += mid - i + 1;  // 关键：有多少个逆序对
            }
        }

        // 剩余部分复制到 temp
        while ( i <= mid )
            temp[ k++ ] = nums[ i++ ];
        while ( j <= right )
            temp[ k++ ] = nums[ j++ ];

        // 把 temp 中排序好的部分拷贝回原数组
        for ( int p = left; p <= right; ++p )
            nums[ p ] = temp[ p ];

        return count;
    }

public:
    int reversePairs( vector< int >& nums )
    {
        vector< int > temp( nums.size() );
        return mergeSortAndCount( nums, temp, 0, nums.size() - 1 );
    }
};

#include <iostream>
#include <vector>

int main() {
    Solution sol;
    vector<int> nums = {7, 5, 6, 4};
    cout << "逆序对总数为：" << sol.reversePairs(nums) << endl; // 输出 5
    return 0;
}

运行结果

逆序对总数为：5