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

#include <algorithm>
#include <cstdint>
#include <random>
#include <vector>
class Solution {
private:
    const int modval = 1000000007;
public:
    void mergeArr(vector<int>& inArr, vector<int>& outArr, int start, int mid, int end, uint64_t* invNumCount)
    {
        int i = start;
        int j = mid+1;
        int k = start;
        // int invNumCount = 0;
        while (i <= mid || j <= end) {
            if (i > mid) {
                outArr[k++] = inArr[j++];
            }
            else if (j > end) {
                outArr[k++] = inArr[i++];
                // invNumCount++;
            }
            else if (inArr[i] <= inArr[j]) {
                outArr[k++] = inArr[i++];
            }
            else {
                *invNumCount += (mid-i+1);
                *invNumCount = (*invNumCount) % modval;
                outArr[k++] = inArr[j++];
            }
        }
        for (int s = start; s <= end; s++) {
            inArr[s] = outArr[s];
        }
        std::cout << "inverse number: " << *invNumCount << endl;
        return;
    }
    void mergeSort(vector<int>& inArr, vector<int>& outArr, int start, int end, uint64_t* invNumCount)
    {
        if (start < end) {
            int mid = (start + end)/2;
            mergeSort(inArr, outArr, start, mid, invNumCount);
            mergeSort(inArr, outArr, mid+1, end, invNumCount);
            mergeArr(inArr, outArr, start, mid, end, invNumCount);
        }
        return;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
        // write code here
        vector<int> inArr = nums;
        vector<int> outArr(nums.size());
        uint64_t invNumCount = 0;
        mergeSort(inArr, outArr, 0, nums.size()-1, &invNumCount);
        return invNumCount;
    }
};