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

几乎又是一次过😋不过想了超级久，要是实战直接寄😅

思路如下：

1. 首先看到“逆序”两个字很自然地想到要用到排序，但这题对复杂度要求比较高，所以考虑归并、快排、堆排。由于之前被快排坑了一次（最坏情况时间复杂度为n2），堆排序用到的情况比较少，所以选择归并排序。
2. 那么排完序之后该怎么办呢？一开始我想的是用二分法，因为看到时间复杂度是nlogn，我就想是不是可以用一层n次遍历的循环套logn次遍历的循环去做呢？想着想着，代码都写差不多了，发现不对！我的二分查找思路是，先把原数组的值和索引位置记录在字典中，然后每次在升序数组中取中点，并向前寻找索引大于中点元素对应的原索引的元素，我以为这样每次都能少遍历一半，结果突然发现对右侧一半数组做同样操作时，会少了跟左侧元素的关系判断，寄！
3. 没办法，只能推倒重来。就在一筹莫展之际，突然灵光一现，我们的目标是要找所有的逆序对，现在我给数组排成升序了就没有逆序对了，这不就是将逆序对消除了吗？！再进一步想，排序过程其实就是将所有逆序对调整顺序的过程！这样就很清楚了，我已经在前面就完成了排序，只需要在合适的位置加上一个变量用于记录有几对逆序对被交换就可以了。

最后再注意一下数值范围就行。复杂度同归并排序。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    unsigned long Merge(vector<int>& left, vector<int>& right, vector<int>& nums) {
        int i = 0, j = 0, k = 0;
        unsigned long res=0;
        while (i < left.size() && j < right.size()) {
            if (left[i] <= right[j]) {
                nums[k++] = left[i++];
            } else {
                res = res + left.size() - i;
                nums[k++] = right[j++];
            }
        }
        while (i < left.size()) nums[k++] = left[i++];
        while (j < right.size())nums[k++] = right[j++];
        return res;
    }

    unsigned long Sort(vector<int>& nums) {
        if (nums.size() == 1)return 0;
        int length = nums.size();
        vector<int> leftnums(nums.begin(), nums.begin() + (length / 2));
        vector<int> rightnums(nums.begin() + (length / 2), nums.end());
        return Sort(leftnums) + Sort(rightnums) + Merge(leftnums, rightnums, nums);
    }

    int InversePairs(vector<int>& nums) {
        // write code here
        // unordered_map<int, int> map;
        // for (int i = 0; i < nums.size(); i++)map[nums[i]] = i;
        unsigned long res;
        res = Sort(nums);
        return res % 1000000007;
    }
};