题解 | 数组中的逆序对

归并排序，先分再和

分：在此处递归得分割数组，直到有序，也就是分割到一个数组只有单个元素

            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);

和：通过 merge(nums, left, mid, right);把分开的数组排序完合回来

到此处我们完成了mergeSort函数，代码如下：

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }

接下来就需要完成merge函数，正是本题找逆序对的关键点

在合的过程中，如果前面元素小于后面元素，则不能构成逆序对，如果后面元素小于前面元素，则可以和前面元素中未排序的元素都可以组成逆序对，即ans = (ans+(mid - i + 1)) % MOD;

    long long ans = 0;
    void merge(vector<int>& nums, int left, int mid, int right) {
        // 此处需要提前分配好空间，否则在21行tmp[k++]，由于未初始化导致段错误
        vector<int> tmp(right-left+1); 
        int k = 0;
        int i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) // 如果前面元素小于后面元素，则不能构成逆序对
            {
                tmp[k++] = nums[i++];
            } 
            else //如果前面元素大于后面元素，可以构成逆序对
            {
                tmp[k++] = nums[j++];
                ans = (ans+(mid - i + 1)) % MOD;
            }
        }
        //将剩下元素插入tmp
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // 将tmp数组写回
        for (int m = 0; m < tmp.size(); m++) {
            nums[left + m] = tmp[m];
        }
    }

最终ac代码如下：

#include <vector>
#define MOD 1000000007
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */

    long long ans = 0;
    void merge(vector<int>& nums, int left, int mid, int right) {
        // 此处需要提前分配好空间，否则在的21行tmp[k++]，由于未初始化导致段错误
        vector<int> tmp(right-left+1); 
        int k = 0;
        int i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) // 如果前面元素小于后面元素，则不能构成逆序对
            {
                tmp[k++] = nums[i++];
            } 
            else //如果前面元素大于后面元素，可以构成逆序对
            {
                tmp[k++] = nums[j++];
                ans = (ans+(mid - i + 1)) % MOD;
            }
        }
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // 将tmp数组写回
        for (int m = 0; m < tmp.size(); m++) {
            nums[left + m] = tmp[m];
        }
    }
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }
    int InversePairs(vector<int>& nums) {
        ans = 0;
        mergeSort(nums, 0, nums.size()-1);
        return (int)ans;
    }
};

小菜b写了一些自己的理解，望大佬指正