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

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    int count = 0;
    int kmod = 1000000007;
    void merge(vector<int>& nums, int start, int mid, int end) {
        int m = nums.size();
        vector<int> temp(end - start +1); //注意temp的大小，是合并之后的数组大小
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {//注意既然是修改nums数组的start->end，j的上限是end
            if (nums[i] > nums[j]) {
                temp[k++] = nums[j++];
                count += mid - i + 1;
                count %= kmod;

            } else {
                temp[k++] = nums[i++];
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= end) {
            temp[k++] = nums[j++];
        }
        for (k = 0, i = start; i <= end;
                ++i, ++k) { //只是修改了nums数组的start->end部分
            nums[i] = temp[k];
        }
    }

    void mergesort(vector<int>& nums, int start, int end) {
        if(end<=start){//注意拆分成一个数字时 end==start
            return;
        }
        if (start < end) {
            int mid = (start + end) / 2;
            mergesort(nums, start, mid);
            mergesort(nums, mid + 1, end);
            merge(nums, start, mid, end);
        }

    }

    int InversePairs(vector<int>& nums) {
        // write code here
        if (nums.size() < 2) {
            return 0;
        }
        mergesort(nums, 0, nums.size() - 1);
        return count;
    }
};