剑指 Offer 51. 数组中的逆序对

题目

传送门

解题思路

这个题解假设你已经明白归并排序的原理。
就以arr = [7,5,6,4]这个例子来讲解为什么一遍归并排序就看可以解决逆序对的问题。
按照归并排序的思路，会将arr分解为arrL = [7,5],arrR = [6,4];
继续分解为arrLL = [7], arrLR = [5]; arrRL = [6], arrRR = [4];
自此分解完成。

接下来合并：

假设i为arrLL的数组下标，j为arrLR的数组下标, index为新数组res的下标，初始值都为0
首先arrLL与arrLR合并，因为arrLL[i] > arrLRj，
所以可以说明arrLL中7及其之后的所有数字都大于arrLR中的5，
也就是说7及其之后的所有元素都可以与5组成逆序对，

所以此时7及其之后的所有元素个数（leftLen - i）即我们要的逆序对数，需要添加到结果sum中。即sum += leftLen - 1

（这也就是此算法高效的地方，一次可以查找到好多次的逆序对数，而且不会重复）

合并之后为arrL=[5,7].

根据上述方法将arrRL和arrRR合并为arrR=[4,6];

现在将arrL和arrR合并为arr：
5 > 4，说明5及其之后的所有元素都能与4组成逆序对；所以sum += （leftLen - 1）；
5 < 6，正常排序，不做处理
7 > 6，说明7及其之后的所有元素都能与6组成逆序对；所以sum += （leftLen - 1）；
7，正常排序，不作处理
最后sum就是所有逆序对的总个数！

代码

class Solution {
public:

    int reversePairs(vector<int>& nums) {
        vector<int> temp(nums.size());      //归并排序的额外数组。
        return mergeSort(nums, 0, nums.size() - 1, temp);
    }
    int mergeSort(vector<int>& nums, int l , int r, vector<int>& temp) {
        if (l < r) {
            int mid  = l + r >> 1;
            int sum = mergeSort(nums, l , mid , temp) + mergeSort(nums, mid + 1, r , temp);

            int k = 0;
            int i = l;
            int j = mid + 1;

            while (i <= mid && j <= r) {
                if (nums[i] <= nums[j]) {
                    temp[k ++ ] = nums[i ++ ];
                }
                else {
                    temp[k ++ ] = nums[j ++ ];
                    sum += (mid - i + 1);       // 归并排序，多的代码，就这一行。
                }
            }
            while (i <= mid) temp[k ++ ] = nums[i ++ ];
            while (j <= r) temp[k ++ ] = nums[j ++ ];
            k = 0;

            while (l <= r) {                //合并后的数组进行更新。
                nums[l ++ ] = temp[k ++ ];
            }
            return sum;
        }

        return 0;
    }
};