题解 | #数组中的逆序对#

方法：归并排序

题目中要求得出一个数组的所有逆序对（前面的数大于后面的数组成一个逆序对），归并排序将数组向下拆分至单个元素的数组，然后向上递归，不断地合并两个数组，直到将整个数组完成排序。

如果是两个有序的数组，我们就可以很容易得到该元素逆序对的数目，而不用一个个进行遍历比较。

时间复杂度：o(nlogⁿ)。递归的深度有logⁿ层，每层需要遍历n个元素进行排序归并，所以时间复杂度为o(nlogⁿ)。

空间复杂度：o(n)。数组需要一个o(n)的空间来保存排序后的数组，每层都需要o(n)，一层排序合并完后可以释放掉该空间，所以虽然递归有logⁿ层，但是只需要o(n)的空间。

class Solution {
  public:
  	//归并排序
    void merge(vector<int>& nums, vector<int>& temp, int left, int right,
               int& ret) {
        if (left >= right)
            return;
		//将数组从中间分为两个数组
        int mid = (left + right) / 2;
	  	//划分
        merge(nums, temp, left, mid, ret);
        merge(nums, temp, mid + 1, right, ret);
	  	//排序合并
        merge_sort(nums, temp, left, mid, right, ret);
    }

    void merge_sort(vector<int>& nums, vector<int>& temp, int left, int mid,
                    int right, int& ret) {
        int l = left;
        int r = mid + 1;
        int k = 0;
        int res = 1000000007;

        while (l <= mid && r <= right) {
		  	//当左侧数组有元素大于右侧数组的元素，可以得到该元素在这个数组的所有逆序对数目
            if (nums[l] > nums[r]) {
                temp[k++] = nums[r++];
			  	//该元素在这个数组的所有逆序对数目
                ret += (mid - l + 1);
                ret %= res;
            } else {
                temp[k++] = nums[l++];
            }
        }
        while (l <= mid)
            temp[k++] = nums[l++];
        while (r <= right)
            temp[k++] = nums[r++];

        for (k = 0, l = left; l <= right; k++, l++)
            nums[l] = temp[k];
    }

    int InversePairs(vector<int>& nums) {
        int ret = 0;
	  	//数组的归并排序需要一个同样大小的数组来保存排序后的数组
        vector<int> temp(nums.size());
        merge(nums, temp, 0, nums.size() - 1, ret);
        return ret;
    }
};