题解 | 数组中的逆序对

#include <cstdint>
class Solution {
public:
    int MergeSort(vector<int> &nums, int len) {
        if(len <= 1) {
            return 0;
        }

        int mid = len / 2;
        // merge [0, mid), [mid, len)
        vector<int> nums_left, nums_right;
        nums_left.reserve(mid);
        nums_right.reserve(len - mid);
        for(int i = 0;i < mid; ++i) {
            nums_left.push_back(nums[i]);
        }
        for(int i = mid;i < len; ++i) {
            nums_right.push_back(nums[i]);
        }

        auto left_cnt = MergeSort(nums_left, mid);
        auto right_cnt = MergeSort(nums_right, len - mid);

        // merge and count 
        nums.clear();
        auto iter_left = nums_left.begin();
        auto iter_right = nums_right.begin();
        int incre_cnt = 0;
        while(iter_left != nums_left.end() || iter_right != nums_right.end()) {
            if(iter_right == nums_right.end() || (
                iter_left != nums_left.end() && *iter_left < *iter_right
            )) {
                nums.push_back(*iter_left);
                ++ iter_left;
            } else {
                nums.push_back(*iter_right);
                incre_cnt = (incre_cnt + nums_left.end() - iter_left) % 1000000007;
                ++ iter_right;
            }
        }


        return (left_cnt + right_cnt + incre_cnt) % 1000000007;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        return MergeSort(nums, nums.size());
    }
};

时间nlogn， 空间n，马上想到归并排序，需要在排序过程中做一点额外的事情