题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例:
输入: [7,5,6,4]
输出: 5

参考代码

本题借用归并排序来解，归并排序参考每日一题：归并排序

class Solution {
private:
    int count;    
public:
    int reversePairs(vector& nums) 
    {
        count = 0;
        vector result(nums.size());
        merge_sort_recursive(nums, result, 0, nums.size()-1);
        
        return count;
    }

    void merge_sort_recursive(vector& arr,  vector& result, int start, int end)
    {
        if(start >= end)
        {
            return;
        }   

        int mid = (start + end) / 2;
        int start1 = start;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = end;

        merge_sort_recursive(arr, result, start1, end1);
        merge_sort_recursive(arr, result, start2, end2);

        //将组左右区间中较小的数字存放到result中，从k开始
        int k = start;
        while(start1 <= end1 && start2 <= end2)
        {
            if(arr[start1] <= arr[start2])
            {
                result[k] = arr[start1];
                start1++;
                k++;
            }
            else
            {
                result[k] = arr[start2];
                //当前值大于，则之后的都大于
                count += (end1 - start1 + 1);
                start2++;
                k++;       
            }
        }

        while(start1 <= end1)
        {
            result[k] = arr[start1];
            start1++;
            k++;
        }

        while(start2 <= end2)
        {
            result[k] = arr[start2];
            start2++;
            k++;
        }

        // 最后，把结果赋值到 arr 中
        for (k = start; k <= end; k++)
            arr[k] = result[k];
    }
};