题解 | 数组中的逆序对

#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    long long GetInversePairs(vector<int>& nums, int left_boundry, int right_boundry) {
        if (left_boundry == right_boundry || right_boundry - left_boundry == 1) return 0;
        int mid = (left_boundry + right_boundry) / 2;
        long long left_ans = GetInversePairs(nums, left_boundry, mid);
        long long right_ans = GetInversePairs(nums, mid, right_boundry);
        int left_it = left_boundry;
        int right_it = mid;
        long long ans = left_ans + right_ans;
        vector<int> new_nums;
        new_nums.reserve(right_boundry - left_boundry);
        while(left_it != mid && right_it != right_boundry) {
            int left_val = nums[left_it];
            int right_val = nums[right_it];
            if (left_val <= right_val) {
                new_nums.push_back(nums[left_it++]);
            } else {
                ans += mid - left_it;
                new_nums.push_back(nums[right_it++]);
            }
        }
        while(left_it != mid) {
            new_nums.push_back(nums[left_it++]);
        }
        while(right_it != right_boundry) {
            new_nums.push_back(nums[right_it++]);
        }
        for (int i = left_boundry; i < right_boundry; ++i) {
            nums[i] = new_nums[i - left_boundry];
        }
        cout << left_boundry << " " << right_boundry << " " << ans << endl;
        return ans;
    }
    int InversePairs(vector<int>& nums) {
        // write code here
        return GetInversePairs(nums, 0, nums.size()) % 1000000007;
    }
};