题目描述

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


示例 1:
输入: [7,5,6,4]
输出: 5
 

限制：
0 <= 数组长度 <= 50000

算法1

暴力双循环是O(n2)的复杂度

但是可以采用归并排序得到更快速的解法。

归并排序的计算思想自然得就蕴含一种得到逆序对的方案

我们先来看看归并排序的过程

在合并两个有序数组中，两个数组中的数组也是按照位置划分，如果第一个数组中的某一个数字比第二个数组的某一个数组大的话 那么这就是一个逆序对
比如上图中的4 7 和4 8 以及 4 5 和 4 6

C++ 代码

class Solution {
public:

    int merge(vector<int>& nums, int l, int r) {
        if (l >= r) return 0;

        int mid = l + r >> 1;
        int res = merge(nums, l, mid) + merge(nums, mid + 1, r);

        vector<int> temp;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (nums[i] <= nums[j]) temp.push_back(nums[i ++ ]);
            else {
                temp.push_back(nums[j ++ ]);
                res += mid - i + 1;
            }
        while (i <= mid) temp.push_back(nums[i ++ ]);
        while (j <= r) temp.push_back(nums[j ++ ]);

        int k = l;
        for (auto x : temp) nums[k ++ ] = x;

        return res;
    }

    int inversePairs(vector<int>& nums) {
        return merge(nums, 0, nums.size() - 1);
    }
};

我的视频空间题解